恒一信息深圳网站建设公司2,建站平台 discuz,西安的电子商城网站建设,题库网站开发目录
一、数据结构和算法
1.什么是数据结构#xff1f;
2.什么是算法#xff1f;
3.数据结构和算法的重要性
二、算法的时间复杂度和空间复杂度
1.算法效率
2.算法的复杂度
3.复杂度在校招中的考察
4.时间复杂度
5.空间复杂度
6.常见复杂度对比
7.复杂度的OJ练…
目录
一、数据结构和算法
1.什么是数据结构
2.什么是算法
3.数据结构和算法的重要性
二、算法的时间复杂度和空间复杂度
1.算法效率
2.算法的复杂度
3.复杂度在校招中的考察
4.时间复杂度
5.空间复杂度
6.常见复杂度对比
7.复杂度的OJ练习 内容专栏《数据结构与算法》 本文概括 讲解数据结构和算法的概念、时间复杂度、空间复杂度、常见复杂度对比。 本文作者花 碟 发布时间2023.4.13 一、数据结构和算法
1.什么是数据结构 数据结构(Data Structure)是计算机存储、组织数据的方式指相互之间存在一种或多种特定关系的数据元素的集合。 就是说方便在内存中管理数据进行增删查改的操作。 2.什么是算法 算法(Algorithm):就是定义良好的计算过程他取一个或一组的值为输入并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果。 3.数据结构和算法的重要性 目前校园招聘笔试一般采用Online Judge形式 一般都是20-30道选择题2道编程题或者3-4道编程题。 可以看出现在公司对学生代码能力的要求是越来越高了大厂笔试中几乎全是算法题而且难度大中小长的笔试中才会有算法题。算法不仅笔试中考察面试中面试官基本都会让现场写代码。而算法能力短期内无法快速提高了至少需要持续半年以上算法训练积累否则真正校招时笔试会很艰难因此算法要早早准备。 数据结构与算法对一个程序员来说的重要性 这篇文章是知乎一篇博主对于数据结构与算法的详细介绍感兴趣的小伙伴们可以看看。
二、算法的时间复杂度和空间复杂度
1.算法效率 如何衡量一个算法的好坏呢比如对于以下斐波那契数列 long long Fib(int N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
} 斐波那契数列的递归实现方式非常简洁但简洁一定好吗那该如何衡量其好与坏呢 2.算法的复杂度 算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。 3.复杂度在校招中的考察 4.时间复杂度
1.时间复杂度的概念 时间复杂度的定义在计算机科学中算法的时间复杂度是一个函数函数表达式它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。 即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。 // 请计算一下Func1中count语句总共执行了多少次
void Func1(int N)
{int count 0;for(int i 0; i N ; i){for(int j 0; j N ; j){count;}}for(int k 0; k 2 * N ; k){count;}int M 10;while(M--){count;}printf(%d\n, count);
}
计算一下Func1执行的基本操作次数是多少 计算Func1执行的基本操作次数函数表达式 F(N) N² 2 * N 10我们接下来给予一些值进行计算F(N)与N的关系 当N 10 F(N) 130 当N 100 F(N) 10210 当N 1000 F(N) 1002010 当N 10000 F(N) 100020010 结论我们发现随着N的增大2*N 10的结果对F(N)的整体结果影响会越来越小其主要影响的一项是N²。 所以实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要估算大概执行次数计算出一个量级就行。那么这里我们使用大O的渐进表示法。 2.大O的渐近表示法 大O符号Big O notation是用于描述函数渐进行为的数学符号。 推导大O阶方法 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。 使用大O的渐进表示法以后Func1的时间复杂度为O(N²) 另外有些算法的时间复杂度存在最好、平均和最坏情况 最坏情况任意输入规模的最大运行次数(上界) 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界) 例如在一个长度为N数组中搜索一个数据x 最好情况1次找到 最坏情况N次找到 平均情况N/2次找到 在实际中一般情况关注的是算法的最坏运行情况需要降低预期考虑最坏的结果。所以数组中搜索数据时间复杂度为O(N) 3.常见时间复杂度计算举例
实例1
// 计算Func2的时间复杂度
void Func2(int N)
{int count 0;for(int k 0; k 2 * N ; k){count;}int M 10;while(M--){count;}printf(%d\n, count);
} 实例1基本操作执行了2N10次通过推导大O阶方法知道时间复杂度为 O(N) 实例2
// 计算Func3的时间复杂度
void Func3(int N, int M)
{int count 0;for(int k 0; k M; k){count;}for(int k 0; k N ; k){count;}printf(%d\n, count);
} 实例2基本操作执行了MN次有两个未知数M和N无法确定M是否远大于(小于)N或者说两者接近所以时间复杂度为 O(MN) 实例3
// 计算Func4的时间复杂度
void Func4(int N)
{int count 0;for(int k 0; k 100; k){count;}printf(%d\n, count);
} 实例3基本操作执行了100次通过推导大O阶方法时间复杂度为 O(1) 注⚠️O1不是1次指的是常数次。 实例4
// 计算strchr的时间复杂度
const char * strchr ( const char * str, int character ); 实例4 在字符串中寻找字符。好的情况在第1次就找到了最坏的情况在尾部找到。基本操作执行最好1次最坏N次时间复杂度一般看最坏时间复杂度为 O(N) 实例5
// 计算BubbleSort的时间复杂度
void BubbleSort(int* a, int n)
{assert(a);for(size_t end n; end 0; --end){int exchange 0;for(size_t i 1; i end; i){if(a[i-1] a[i]){Swap(a[i-1], a[i]);exchange 1;}}if(exchange 0)break;}
} 实例5基本操作执行最好N次即第一趟进去查找已经是有序的数字了最好情况是O(N)最坏的情况呢一共需要N - 1趟嘛从N - 1 趟开始执行N - 1次、N - 2、N - 3 …… 3、2 、1可以看出来这是一个等差数列求和最坏执行了N*(N-1)/2次 通过推导大O阶方法时间复杂度一般看最坏故时间复杂度为 O(N^2) 实例6
// 计算BinarySearch的时间复杂度
int BinarySearch(int* a, int n, int x)
{assert(a);int begin 0;int end n-1;//[begin, end]begin和end是左闭右闭区间因此有号while(begin end){int mid begin ((end-begin)1);if (a[mid] x)begin mid1;else if (a[mid] x)end mid-1;elsereturn mid;}return -1;
} 实例6 基本操作执行最好1次最坏O(logN)次时间复杂度为 O(log₂N)。pslogN在算法分析中表示是底数为2对数为N。有些地方会写成lgN 实例7
// 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if(0 N)return 1;return Fac(N-1)*N;
} 实例7 通过计算分析发现基本操作递归了N次每次调用执行常数次所以时间复杂度为O(N) 实例8
// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
} 画图分析 实例8 斐波那契数列每一项都是递归调用两个子项。我们可以将斐波那契数列的调用过程大致用画图画出来函数往后调用次数会越来越多但是到最后几次快调用完了的时候右边的部分会提前加结束调用次数会大幅度减少呈现一个三角形灰色部分为数据缺失部分画图不够准确但大体思想可以这么表示。我们发现其中调用的每一层是2的倍数可以看作是一个等比数列运用错位相减的方法求出基本操作递归了2^(N - 1) - 1次故时间复杂度为O(2^N) 5.空间复杂度 1.空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 2.空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。 3.空间复杂度计算规则基本跟时间复杂度类似也使用大O渐进表示法。注意⚠️函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显示申请的额外空间来确定。 空间复杂度计算举例
实例1
// 计算BubbleSort的空间复杂度
void BubbleSort(int* a, int n)
{assert(a);for(size_t end n; end 0; --end){int exchange 0;for(size_t i 1; i end; i){if(a[i-1] a[i]){Swap(a[i-1], a[i]);exchange 1;}}if (exchange 0)break;}
} 实例1 使用了常数个额外空间所以空间复杂度为 O(1) 实例2
// 计算Fibonacci的空间复杂度
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{if(n0)return NULL;long long * fibArray (long long *)malloc((n1) * sizeof(long long));fibArray[0] 0;fibArray[1] 1;for(int i 2; i n ; i){fibArray[i] fibArray[i - 1] fibArray [i - 2];}return fibArray;
} 实例2动态开辟了N个空间空间复杂度为 O(N) 实例3
// 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{if(N 0)return 1;return Fac(N-1)*N;
} 实例3递归调用了N次开辟了N个栈帧每个栈帧使用了常数个空间。空间复杂度为 O(N) 6.常见复杂度对比
一般算法常见的复杂度如下 7.复杂度的OJ练习 1.消失的数字 17.04 消失的数字_点击链接跳转 2.轮转数组 189.轮转数组_点击链接跳转 好啦本篇文章就到此为止啦~ 感谢大家的支持希望对你有帮助如有什么疑问可以在评论区or私信告诉我~~
