N = 10 F(N) = 100 N = 100 F(N) = 10000 N = 1000 F(N) = 1000000
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)
2.3常见时间复杂度计算举例
实例1
计算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);
}
基本操作执行了2*N + 10次，而通过推导大O阶方法
用常数1取代加法常数，得到2*N + 1
只保留最高阶项，得到2*N
将最高阶项的系数变为1，得到N
所以最后的时间复杂度是O(N)
实例2：计算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);
}
时间复杂度为O(N+M)
实例3：计算Func4的时间复杂度
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%d\n", count);
}
用常数1替代100，时间复杂度是O(1)
实例4：计算strchr的时间复杂度
const char* strchr(const char* str, int character)
{
while (*str != character)
{
str++;
}
return str;
}
最快执行了1次，最慢执行了N次，所以时间复杂度是O(N)
实例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;
}
}
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n - 1;
// [begin, end]：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;
}
假如有序数组有N个数，那么查找一次就会将数组的范围缩小一半，直到最后只剩下一个数
可以这么用数字表示：
N / 2 / 2 / 2 / 2 / 2 / 2 ...... / 2 / 2 = 1
假设查找了x次，也就是每次将数组缩小一半(除以2)这个基本操作执行了x次，那么这个x与N之间的关系是2^x = N
那么x = logN，这里默认底数为2
所以时间复杂度是O(logN)
实例7：计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}
基本操作递归了N次，所以时间复杂度为O(N)
实例8：计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}
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 = 10 F(N) = 100 N = 100 F(N) = 10000 N = 1000 F(N) = 1000000
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)
2.3常见时间复杂度计算举例
实例1
计算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);
}
基本操作执行了2*N + 10次，而通过推导大O阶方法
用常数1取代加法常数，得到2*N + 1
只保留最高阶项，得到2*N
将最高阶项的系数变为1，得到N
所以最后的时间复杂度是O(N)
实例2：计算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);
}
时间复杂度为O(N+M)
实例3：计算Func4的时间复杂度
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
++count;
}
printf("%d\n", count);
}
用常数1替代100，时间复杂度是O(1)
实例4：计算strchr的时间复杂度
const char* strchr(const char* str, int character)
{
while (*str != character)
{
str++;
}
return str;
}
最快执行了1次，最慢执行了N次，所以时间复杂度是O(N)
实例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;
}
}
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n - 1;
// [begin, end]：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;
}
假如有序数组有N个数，那么查找一次就会将数组的范围缩小一半，直到最后只剩下一个数
可以这么用数字表示：
N / 2 / 2 / 2 / 2 / 2 / 2 ...... / 2 / 2 = 1
假设查找了x次，也就是每次将数组缩小一半(除以2)这个基本操作执行了x次，那么这个x与N之间的关系是2^x = N
那么x = logN，这里默认底数为2
所以时间复杂度是O(logN)
实例7：计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}
基本操作递归了N次，所以时间复杂度为O(N)
实例8：计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{
if (N < 3)
return 1;
return Fib(N - 1) + Fib(N - 2);
}
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;
}
}
