目录一、算法效率1.如何衡量一个算法的好坏2.时间复杂度1时间复杂度的概念2大O的渐进表示法本质计算时间复杂度次数属于哪个量级level3常见时间复杂度计算①计算Func2的时间复杂度②计算Func3的时间复杂度③计算Func4的时间复杂度④计算strchr的时间复杂度⑤计算BubbleSort的时间复杂度⑥计算BinarySearch的时间复杂度⑦计算递归Fac的时间复杂度⑧计算斐波那契递归Fib的时间复杂度3.空间复杂度①计算BubbleSort的空间复杂度②计算Fibonacci的空间复杂度③计算阶乘递归的空间复杂度常见的空间复杂度数据结构data Structure是计算机存储、组织数据的方式指相互之间存在一种或多种特定关系的数据元素的集合。算法Algorithm就是定义良好的计算过程取一个或一组的值为输入并产生一个或一组值作为输出。简单来说算法就是一系列计算步骤用来将输入数据转化成输出结果。一、算法效率1.如何衡量一个算法的好坏算法咋编写成可执行程序后运行时需要消耗时间资源和空间内存资源因此衡量一个算法的好坏一般是从时间和空间两个维度衡量的即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢空间复杂度主要衡量一个算法运行时所需要的额外空间。时间复杂度和空间复杂度中我们更关注时间复杂度2.时间复杂度1时间复杂度的概念时间复杂度的定义在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。//计算一下函数Func1中count语句总共执行了多少次 int 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 N * 2; k) { count; } int M 10; while (M--) { count; } printf(%d\n, count); }Func1执行的基本操作次数F(N) N^2 2 * N 10N 10 时F(N) 130N 100 时F(N) 10210N 1000 时F(N) 1002010实际我们计算时间复杂度时并不一定需要计算精确的执行次数只需要大概执行次数这里使用大O的渐进表示法。2大O的渐进表示法大O符号big O notation是用于描述函数渐进行为的数学符号。推导大O阶方法1.用常数1取代运行时间中的所有加法常数2.在修改后的运行次数函数中只保留最高阶项3.如果最高阶项存在且不是1则去除与这个项目相乘的常数得到的结果就是大O阶。使用大O阶渐进表示法后Func1的时间复杂度为O(N^2)N 10 时F(N) 100N 100 时F(N) 10000N 1000 时F(N) 1000000通过上面我们可以发现大O的渐进表示法去掉了那些对结果影响不大的项简洁明了的表示出了执行次数。另外有些算法的时间复杂度存在最好、平均和最坏情况最坏情况任意输入规模的最大运行次数上界平均情况任意输入规模的期望运行次数最好情况任意输入规模的最小运行次数下界例如在一个长度为N的数组中搜索一个数据X最好情况一次找到最坏情况N次找到平均情况N/2次找到在实际中一般关注的是算法的最坏运行情况所有数组中搜索数据的时间复杂度为O(N)本质计算时间复杂度次数属于哪个量级level常见的量级O(1) 常数阶O(n) 线性阶O(n^2) 平方阶O(logn) 对数阶O(nlogn) nlogn阶O(n^3) 立方阶O(2^n) 指数阶3常见时间复杂度计算①计算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); }基本操作执行了(2N10)次时间复杂度为O(N)②计算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); }基本操作执行了(MN)次有两个未知数M和N时间复杂度为O(MN)也可以写成O(max(m,n))如果M远大于N时间复杂度为O(M)如果N远大于M时间复杂度为O(N)③计算Func4的时间复杂度void Func4(int N) { int count 0; for (int k 0; k 100; k) { count; } printf(%d\n, count); }基本操作执行了10次时间复杂度为O(1)注O(1)不是代表一次而是代表常数次。-④计算strchr的时间复杂度在字符串中查找一个字符const char* strchr(const char* str, int character);基本操作执行了最好1次最坏N次时间复杂度一般看最坏时间复杂度为O(N)⑤计算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]) { int temp a[i]; a[i] a[i - 1]; a[i - 1] temp; exchange 1; } } if (exchange 0) { break; } } }基本操作执行了最好N次最坏(N*(N)/2)次时间复杂度为O(N^2)⑥计算BinarySearch的时间复杂度二分查找int BinarySearch(int* a, int n, int x) { assert(a); int begin 0; int end n - 1; // [begin, end]是左闭右闭区间因此有号 while (begin end) { int mid begin ((end - begin) 1);//防溢出写法 if (a[mid] x) { begin mid 1; } else if (a[mid x]) { end mid - 1; } else { return mid; } } return -1; }基本操作执行了最好1次最坏O(logN)次时间复杂度为O(logN)注logN在算法分析中表示的是底数为2对数为N。有些地方会写成lgN其他底数不能省略但很少出现二分查找在实际中不太实用因为二分查找必须使用数组结构不方便插入删除二分查找本质是区间查找如果是左闭右闭区间就一直保持左闭右闭区间如果是左闭右开区间就一直保持左闭右开区间。⑦计算递归Fac的时间复杂度long long Fac(size_t N) { if (N 0) { return 1; } return Fac(N - 1); }递归时间复杂度所有递归调用次数累加递归操作执行了N次时间复杂度为O(N)⑧计算斐波那契递归Fib的时间复杂度long long Fib(size_t N) { if (N 3) { return 1; } return Fib(N - 1) Fib(N - 2); }递归操作执行了2^N次时间复杂度为O(2^N)3.空间复杂度空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。①计算BubbleSort的空间复杂度void BullbeSort(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]) { int temp a[i - 1]; a[i - 1] a[i]; a[i] temp; exchange 1; } } if (exchange 0) { break; } } }使用了常数个额外空间空间复杂度为O(1)②计算Fibonacci的空间复杂度返回斐波那契数列的前n项long long* Fibonacci(size_t n) { if (n 0) { return NULL; } long long* fibArray (long long*)malloc((n 1) * 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; }动态开辟了N个空间空间复杂度有为O(N)③计算阶乘递归的空间复杂度long long Fac(size_t N) { if (N 0) { return 1; } return Fac(N - 1) * N; }递归调用了N次开辟了N的栈帧每个栈帧使用了常数个空间空间复杂度为O(N)常见的空间复杂度O(1) 常数个O(N) 额外的数组O(N^2) 额外开辟二维数组完