阅读量:0
文章目录
算法复杂度
1.数据结构
1.1 数据结构（数据的管理）
数据结构(Data Structure)是计算机存储、组织数据的⽅式，指相互之间存在⼀种或多种特定关系的数据元素的集合。数据结构eg：
线性表、树、图、哈希等。
1.2算法（取，管理数据）
算法(Algorithm):就是定义良好的计算过程，他取⼀个或⼀组的值为输⼊，并产⽣出⼀个或⼀组值作为输出。
how学好数据结构？（这可是干货，嘿嘿）
1，死磕代码。2，画图＋思考。
2.算法效率
2.1复杂度的概念
(1).衡量⼀个算法的好坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
(2).时间复杂度主要衡量⼀个算法的运⾏快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。
3.时间复杂度
在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间。
3.1时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运⾏时间呢？
(1).因为程序运⾏时间和编译环境和运⾏机器的配置都有关系.
(2). 同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同.
(3). 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估.
计算程序能代表增⻓量级的⼤概执⾏次数，复杂度的表⽰通常使⽤⼤O的渐进表⽰法。
3.2⼤O的渐进表示法
⼤O符号（Big O notation）：是⽤于描述函数渐进⾏为的数学符号。
推导⼤O阶规则:
- 时间复杂度函数式T(N)中，只保留最⾼阶项，去掉那些低阶项，因为当N不断变⼤时，低阶项对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
- 如果最⾼阶项存在且不是1，则去除这个项⽬的常数系数，因为当N不断变⼤，这个系数对结果影响越来越⼩，当N⽆穷⼤时，就可以忽略不计了。
- T(N)中如果没有N相关的项⽬，只有常数项，⽤常数1取代所有加法常数。eg:O(100)= O(1);用O（1）来表示常数。
3.3 时间复杂度计算⽰例
3.3.1 ⽰例1
// 计算Func2的时间复杂度？ void Func2(int N) { int count = 0; for (int k = 0; k < 2 * N ; ++ k)//FOR循环执行次数为2N { ++count; } int M = 10; while (M--) //while循环次数为10 { ++count; } printf("%d\n", count); } Func2的时间复杂度为： O(N)
解析：Func2执⾏的基本操作次数：T (N) = 2N + 10,(2N:FOR循环执行次数为2N；10：while循环次数为10)根据推导规则第3条得出,Func2的时间复杂度为： O(N).
3.3.2 ⽰例2
// 计算Func3的时间复杂度？ void Func3(int N, int M) { int count = 0; for (int k = 0; k < M; ++ k) //FOR循环执行次数为M { ++count; } for (int k = 0; k < N ; ++k)//第二个for循环循环次数为N { ++count; } printf("%d\n", count); } Func2的时间复杂度为： O(N)。
解析：Func3执⾏的基本操作次数：T (N) = M + N;(FOR循环执行次数为M，第二个for循环循环次数为N);Func2的时间复杂度为： O(N)。
3.3.3 ⽰例3
// 计算Func4的时间复杂度？ void Func4(int N) { int count = 0; for (int k = 0; k < 100; ++ k) //执行次数为100 { ++count; } printf("%d\n", count); } Func2的时间复杂度为： O(1)。
解析：
T (N) = 100（for循环执行次数为100）根据推导规则第1条得出Func2的时间复杂度为： O(1)。
3.3.4 ⽰例4
// 计算strchr的时间复杂度？ const char * strchr ( const char * str, int character) { const char* p_begin = s; while (*p_begin != character)//三种范围区间 { if (*p_begin == '\0') return NULL; p_begin++; } return p_begin; } 最好情况： O(1)
最坏情况： O(N)
平均情况： O(N)
解析：
strchr执⾏的基本操作次数：
1）若要查找的字符在字符串第⼀个位置，则：T (N) = 1
2）若要查找的字符在字符串最后的⼀个位置，则：T (N) = N
3）若要查找的字符在字符串中间位置，则：T (N) =2N
因此：strchr的时间复杂度分为：
最好情况： O(1)，最坏情况： O(N)，平均情况： O(N)。
从这道例题得出结论：
通过上⾯我们会发现，有些算法的时间复杂度存在最好、平均和最坏情况。
最坏情况：任意输⼊规模的最⼤运⾏次数(上界)。
平均情况：任意输⼊规模的期望运⾏次数。
最好情况：任意输⼊规模的最⼩运⾏次数(下界)。
⼤O的渐进表⽰法在实际中⼀般情况关注的是算法的上界，也就是最坏运⾏情况。
3.3.5 ⽰例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; } } BubbleSort的时间复杂度取最差情况为： O(N2 )。
解析：
BubbleSort执⾏的基本操作次数：1）若数组有序，则：T (N) = N。
2）若数组有序且为降序，则：
T (N) =2N ∗ (N + 1)。
3）若要查找的字符在字符串中间位置，则：因此：BubbleSort的时间复杂度取最差情况为： O(N2 )。
3.3.6 ⽰例6
void func5(int n) { int cnt = 1; while (cnt < n) { cnt *= 2; } } func5的时间复杂度取最差情况为：O(log2 n);
解析：
假设执⾏次数为 x ，则 2x = n；
因此执⾏次数： x = log n。
3.3.7 ⽰例7
// 计算阶乘递归Fac的时间复杂度？ long long Fac(size_t N) { if(0 == N) return 1; return Fac(N-1)*N; } 阶乘递归的时间复杂度为： O(n).
解析:
调⽤⼀次Fac函数的时间复杂度为 O(1);⽽在Fac函数中，存在n次递归调⽤Fac函数.
4.空间复杂度
空间复杂度是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。
空间复杂度计算规则基本跟实践复杂度类似，也使⽤⼤O渐进表⽰法。
注意：函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定。
4.1 空间复杂度计算⽰例
4.1.1 ⽰例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; } } 空间复杂度为 O(1)；
解析：
函数栈帧在编译期间已经确定好了，只需要关注函数在运⾏时额外申请的空间。BubbleSort额外申请的空间有exchange等有限个局部变量，使用了常数个额外空间。
4.1.2 ⽰例2
// 计算阶乘递归Fac的空间复杂度？ long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; //递归调用了N次 } 空间复杂度为： O(N)。
解析：
Fac递归调⽤了N次，额外开辟了N个函数栈帧，每个栈帧使⽤了常数个空间。
5.常⻅复杂度对比
6. 复杂度算法题
思路1
时间复杂度 O(n2 )
循环K次将数组所有元素向后移动⼀位（代码不通过原因:时间超时了）
void rotate(int* nums, int numsSize, int k) { while(k--) { int end = nums[numsSize-1]; for(int i = numsSize - 1;i > 0 ;i--) { nums[i] = nums[i-1]; } nums[0] = end; } } 思路2：
空间复杂度 O(n)
申请新数组空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中。newArr[(i + k) % numsSize] = nums[i];（关键）
void rotate(int* nums, int numsSize, int k) { int newArr[numsSize]; for (int i = 0; i < numsSize; ++i) { newArr[(i + k) % numsSize] = nums[i];//这一部超妙 } for (int i = 0; i < numsSize; ++i) { nums[i] = newArr[i]; } } 思路3：如下图，参考下面代码及注释
空间复杂度 O(1)
void reverse(int* nums,int left,int right) {//函数定义用逗号 while(left<right) { int tmp =nums[left]; nums[left] = nums[right]; nums[right] = tmp; left++; right--; } } void rotate(int* nums, int numsSize, int k) { k = k%numsSize; //前n-k个数据逆置 reverse(nums,0,numsSize-k-1);//函数调用用逗号 //后k个数据逆置 reverse(nums,numsSize-k,numsSize-1); //整体逆置 reverse( nums,0,numsSize-1); } 总结：
以上就是关于数据结构中算法复杂度的全部内容了，写的超详细，博主写了两天，喜欢的兄弟们，可以一键三连。 