本文主要是介绍算法复杂度 —— 数据结构前言、算法效率、时间复杂度、空间复杂度、常见复杂度对比、复杂度算法题(旋转数组),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
一、数据结构前言
1、数据结构
2、算法
3、学习方法
二、 算法效率
引入概念:算法复杂度
三、时间复杂度
1、大O的渐进表示法
2、时间复杂度计算示例
四、空间复杂度
计算示例:空间复杂度
五、常见复杂度对比
六、复杂度算法题(旋转数组)
1、思路1
2、思路2
3、思路3
一、数据结构前言
1、数据结构
2、算法
3、学习方法
第一、多找题刷题,如刷题网站:牛客网、LeetCode等;第二、死磕代码;第三、画图+思考
二、 算法效率
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;//数组中最后一个数据挪到第一位}
}
代码点击执行可以通过,然而点击提交却无法通过,这就是衡量算法好坏,涉及到算法复杂度。
引入概念:算法复杂度
- 算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。
- 因此衡量⼀个算法的好坏,⼀般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。
- 时间复杂度主要衡量⼀个算法的运行快慢,而空间复杂度主要衡量⼀个算法运行所需要的额外空间。
- 在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度,重点在于时间复杂度。
三、时间复杂度
- 因为程序运⾏时间和编译环境和运行机器的配置都有关系,比如同⼀个算法程序,用⼀个老编译器进行编译和新编译器编译,在同样机器下运行时间不同(无法算出精确的运行时间)。
- 同⼀个算法程序,用⼀个老低配置机器和新高配置机器,运行时间也不同。
- 并且时间只能程序写好后测试,不能写程序前通过理论思想计算评估。
以下的典型代码能够很好的体现这一点:
#include <stdio.h>
#include <time.h>int main()
{//计算程序运行时间int begin = clock();//clock()函数用来保存运行的时间int count = 0;for(int i = 0;i < 100000000;i++){count++;}int end = clock();printd("time:%d\n",end - begin);return 0;
}
VS中有两个版本,版本的不同会影响程序运行的时间。在VS中的Debug版本中,运行时是需要加上调试信息的时间的,时间会长一点;而在Release版本中,不会增加调试信息的时间,运行效率是很高的。
VS中的Debug版本:
VS中的Release版本:
- 算法的时间复杂度是⼀个函数式T(N),它计算了程序的执行次数。
- 通过c语言编译链接章节学习,算法程序被编译后生成二进制指令,程序运行,就是CPU执行这些编译好的指令。
- 通过程序代码或者理论思想计算出程序的执⾏次数的函数式T(N),假设每句指令执行时间基本⼀样(实际中有差别,但是微乎其微),那么执行次数和运行时间就是等比正相关,这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣。
- 比如解决⼀个问题的算法a程序T(N) = N,算法b程序T(N) = N^2,那么算法a的效率⼀定优于算法b。一次定义的变量也算一个时间复杂度,为1,可忽略不计。
// 请计算⼀下Func1中++count语句总共执⾏了多少次?
void Func1(int N)
{int count = 0;for (int i = 0; i < N ; ++ i){for (int j = 0; j < N ; ++ j){++count;}}//N^2for (int k = 0; k < 2 * N ; ++ k){++count;}//2Nint M = 10;while (M--)//10{++count;}
}
- 实际中计算时间复杂度时,计算的也不是程序的精确的执行次数,精确执行次数计算起来还是很麻烦的(不同的⼀句程序代码,编译出的指令条数都是不⼀样的),计算出精确的执行次数意义也不大。
- 因为计算时间复杂度只是想比较算法程序的增长量级,也就是当N不断变大时T(N)的差别,上面我们已经看到了当N不断变大时常数和低阶项对结果的影响很小。
- 所以只需要计算程序能代表增长量级的大概执行次数,复杂度的表示通常使用大O的渐进表示法。
1、大O的渐进表示法
大O符号(Big O notation):是用于描述函数渐进行为的数学符号。
- 时间复杂度函数式T(N)中,只保留最高阶项,去掉那些低阶项,这里的高阶项和低阶项是相对来说的,因为当N不断变大时, 高阶项对结果的影响越来越大,低阶项对结果影响越来越小,当N无穷大时,就可以忽略不计了。
- 如果最高阶项存在且不是1,则去除这个项目的常数系数,因为当N不断变大,这个系数对结果影响越来越小,当N无穷大时,就可以忽略不计了。
- T(N)中如果没有N相关的项目,只有常数项(无论多大),用常数1取代所有加法常数。
我们所讲的非常大的数字,一般在数学中取的是极限。
通过以上⽅法,可以得到 Func1 的时间复杂度为: O(N^2 )
2、时间复杂度计算示例
// 计算Func2的时间复杂度?
void Func2(int N)
{int count = 0;for (int k = 0; k < 2 * N ; ++ k)//2N{++count;}int M = 10;while (M--)//10{++count;}printf("%d\n", count);
}
// 计算Func3的时间复杂度?
void Func3(int N, int M)
{int count = 0;for (int k = 0; k < M; ++ k)//M 变量{++count;}for (int k = 0; k < N ; ++k)//N 变量{++count;}printf("%d\n", count);
}
// 计算Func4的时间复杂度?
void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++ k)//常数则为1{++count;}printf("%d\n", count);
}
// 计算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;
}
- 若要查找的字符在字符串第⼀个位置,则: T (N) = 1
- 若要查找的字符在字符串最后的⼀个位置, 则: T (N) = N
- 若要查找的字符在字符串中间位置,则: T (N) = 2N
实例五:
冒泡排序的外层循环(控制次数)控制内层循环多少次(执行次数),只需算内层循环即可。
// 计算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执行的基本操作次数:
- 若数组有序,则: T (N) = N
- 若数组有序且为升序,则: T (N) = (N ∗ (N + 1))/2
- 若要查找的字符在字符串中间位置,则因此BubbleSort的时间复杂度取最差情况为: O(N^2 )
综上同理可得,Func1的外层循环(控制次数)也是控制内层循环多少次(执行次数),只需算内层循环即可,即得内层相加的结果为N*N。
实例六:
void func5(int n)
{int cnt = 1;while (cnt < n){cnt *= 2;}
}
- 当n接近⽆穷⼤时,底数的大小对结果影响不大。
- 因此,⼀般情况下不管底数是多少都可以省略不写,即可以表⽰为 log n 。
- 不同书籍的表示方式不同,以上写法差别不大,我们建议使用 log n。
- 以上几种写法都是正确的,对于计算机而言,这里的底数大小可以忽略不计,即可去掉。其次,键盘或代码中是无法输入底数的。用数学层面来说就是换底公式的运用使底数对结果的影响不大。
// 计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N)
{if(0 == N)return 1;return Fac(N-1)*N;
}
四、空间复杂度
- 空间复杂度也是⼀个数学表达式,是对⼀个算法在运行过程中因为算法的需要额外临时开辟的空间。
- 空间复杂度不是程序占用了多少bytes的空间,因为常规情况每个对象大小差异不会很大,所以空间复杂度算的是变量的个数。
- 空间复杂度计算规则基本跟实践复杂度类似,也使用大O渐进表示法。
计算示例:空间复杂度
实例一:
// 计算BubbleSort的时间复杂度?
void BubbleSort(int* a, int n)
{assert(a);//assert断言不需要申请空间for (size_t end = n; end > 0; --end)//1{int exchange = 0;//1for (size_t i = 1; i < end; ++i)//1{if (a[i-1] > a[i]){Swap(&a[i-1], &a[i]);exchange = 1;}}if (exchange == 0)break;}
}
// 计算阶乘递归Fac的空间复杂度?
long long Fac(size_t N)
{if(N == 0)return 1;return Fac(N-1)*N;
}
int func(int n)
{int arr[n] = malloc(sizeof(int)*n);//空间复杂度也为O(N)
}
五、常见复杂度对比
六、复杂度算法题(旋转数组)
1、思路1
- 时间复杂度 O(N^2 )
- 循环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;} }
根据第五大点的时间复杂度 O(N^2 )图表,运行时会超出时间限制:
2、思路2
- 空间复杂度 O(N);时间复杂度O(N)
- 申请新数组空间,先将后k个数据放到新数组中,再将剩下的数据挪到新数组中
void rotate(int* nums, int numsSize, int k) {int newArr[numsSize];for (int i = 0; i < numsSize; ++i)//N{newArr[(i + k) % numsSize] = nums[i];}for (int i = 0; i < numsSize; ++i)//N{nums[i] = newArr[i];} }
交换前:
交换后:
时间复杂度少的原因:
3、思路3
- 空间复杂度 O(1);时间复杂度O(N)
- 前n-k个逆置: 4 3 2 1 5 6 7
- 后k个逆置 :4 3 2 1 7 6 5
- 整体逆置 : 5 6 7 1 2 3 4
void reverse(int* nums,int left,int right) {while(left < right){//left和right指向的数据要进行交换int tmp = nums[left];nums[left] = nums[rightend];nums[right] = tmp;left++;right--;} }void rotate(int* nums, int numsSize, int k) {k = k%numsSize;reverse(nums,0,numsSize-k-1);//传的是数组的下标//前n-k个逆置reverse(nums,numsSize-k,numsSize-1);//后k个逆置reverse(nums,0,numsSize-1);//整体逆置 }
这篇关于算法复杂度 —— 数据结构前言、算法效率、时间复杂度、空间复杂度、常见复杂度对比、复杂度算法题(旋转数组)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!