时间复杂度和空间复杂度及多道例题讲解 债券期货价格计算例题及答案解析视频讲解

void Func2(int N){ int count = 0; for (int k = 0; k < 2 * N ; ++ k) { ++count; } int M = 10; while (M--) { ++count; } printf("%d ", count);}

 2N+10去掉常数项10拿掉最高高阶项N的系数2就变成了O（N）。

第二题：

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 ", count);}

第三题：

void Func4(int N){ int count = 0; for (int k = 0; k < 100; ++ k) { ++count; } printf("%d ", count);}

 很明显K 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个数换到指定顺序的位置，总次数是n-1趟原因是如果有10个数要排序那么排9个数剩下一个数的位置自己就被换到相应的位置。而在每一趟中排完一个数后就减少1次，所以每一趟的次数是N-1,N-2,N-3......1,而一趟冒泡排序的次数又是N-1，所以时间复杂度是(N-1)*(N-1）为O（N^2），为什么要用N-1不用N-2或者后面的计算呢？原因是时间复杂度计算的是最差的结果。

第五题：

int BinarySearch(int* a, int n, int x){ assert(a); int begin = 0; int end = n-1; // [begin, end]：begin和end是左闭右闭区间，因此有=号 while (begin >1); if (a[mid] < x) begin = mid+1; else if (a[mid] > x) end = mid-1; else return mid; } return -1;}

要计算二分查找法的时间复杂度首先要明白其原理，二分查找就是根据中间值看下次查找的区间在中间值的左边还是右边，明天这个我们就知道每次查找的次数都会除2，比如有N个数，那么要找到这个数就需要N/2/2/2/2/2...,假设查找了X次，N=2*2*2*2*2*2(乘2的x次方）也就是N=2^X，X=log2N（log以2为底N的对数）所以二分查找的时间复杂度为O（logN）由于计算机不好打出以2为底所以直接为logN，当有底数不是2的时候需要写出底数.

第六题：

long long Fac(size_t N){ if(0 == N) return 1; return Fac(N-1)*N;}

计算阶乘的时间复杂度，每次N递归从N-1,N-2,N-3,N-4....0,很多人将此复杂度错误认为N^2，其实在这里每次递归乘的N都只是一个常数比如N为10的时候F（9）*10然后F（9）为F（8）*10一直往下递归，在这我们就能看出来时间复杂度是O（N）；

第七题：

long long Fib(size_t N){ if(N < 3) return 1; return Fib(N-1) + Fib(N-2);}

计算斐波那契数列的时间复杂度我们需要画个图：

如图我们可以看出斐波那契数列的时间复杂度为O（2^N）。

第八题：

设某算法的递推公式是T(n)=T(n-1)+n，T(0)=1，则求该算法中第n项的时间复杂度为

此题与阶乘类似，每次递归的是T（n-1）对于加的常数不做处理，从n-1,n-2,n-3......0所以时间复杂度为O(N).

第八题：

给定一个整数sum，从有N个有序元素的数组中寻找元素a，b，使得a+b的结果最接近sum，最快的平均时间复杂度是

此题计算的是最快的时间复杂度，那么在一个有序数组中找接近SUM的和我们只需要两个指针一个从头开始一个从尾开始一起遍历，那么最快就是O（N）。

第九题：

void fun(int n) { int i=l; while(i a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; }}

在冒泡排序中使用的额外空间有end exchange i三个变量的空间，所以空间复杂度为O（1）；

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