时间复杂度经典例题分析
规则
例题1：循环
void Func1(int N) { int count = 0; for (int k = 0; k < 2 * N; ++k) { ++count; } int M = 10; while (M--) { ++count; } printf("%d\n", count); } 复制代码
共执行2*N+10次
常数可以忽略不计 O(2*N+10) ==>O(N)
时间复杂度为：O(N)
例题2：循环
void Func2(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); } 复制代码
共执行M+N次，由于M和N的大小未知，所以时间复杂度为：O(M+N)
- 情况1：M>>>N，则时间复杂度为：O(M)
- 情况2：N>>>M，则时间复杂度为：O(N)
- 情况3：M和N差不多大 则时间复杂度为：O(M)或者O(N)
例题3：循环
void Func3(int N) { int count = 0; for (int k = 0; k < 100; ++k) { ++count; } printf("%d\n", count); }
共执行100次，常数次->时间复杂度为0(1)
O(1)不是代表算法运行一次，而是常数次
例题4:strchr
strchr作用：在字符串中查找字符
返回字符第一次出现的位置，找不到返回NULL
模拟实现strchr
#include<stdio.h> #include<assert.h> char* my_strchr(const char* str, char c) { assert(str); char* tmp = str; while (*tmp) { if (*tmp == c) { return tmp; } else { tmp++; } } return NULL; } int main() { char* str = "Mangoa"; printf("%s\n", my_strchr(str, 'a')); return 0; } 复制代码
回到正题：
// 计算strchr的时间复杂度？ const char * strchr(const char * str, int character); 复制代码
最好情况：1次找到
平均情况：找了N/2次
最坏情况：找了N次
当一个算法随着输入不同，时间复杂度不同，时间复杂度做悲观预测，看最坏情况。
所以时间复杂度为O(N)
例题5：冒泡排序
冒泡排序思想：相邻元素进行比较
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; } } 复制代码
每一趟冒泡排序可以让一个数在应该在的位置，每一趟可以排序好一个元素，有N个数，只需只需N-1次即可
第一趟：比较N-1个数
第二趟：比较N-2个数
...
第N-1趟：比较1个数
等差数列：F(N) = N*(N-1)/2
所以时间复杂度为：0(N^2)
例题6：二分查找(折半查找)
二分查找：每次减少1/2的查找范围，直到找到/找不到
int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n - 1; while (begin < end) { int mid = begin + ((end - begin) >> 1); if (a[mid] < x) begin = mid + 1; else if (a[mid] > x) end = mid; else return mid; } return -1; } 复制代码
关于二分查找
前提：有序
在1000个数中找1个数 ->最坏查找次数：10次
在100W个数中找1个数 ->最坏查找次数：20次
在10亿个数中找1个数 ->最坏查找次数：30次
2^10 = 1024 2^20 约等于100W 实际大于100W 2^30 约等于10亿 复制代码
问：在14亿有序的人口中查找一个人，最多查找多少次
31次， 2^31 约等于20亿
