1. 如何衡量算法效率
算法与程序的联系
算法是解决一个问题所定义的计算步骤, 这些计算步骤通过计算机语言描述编写成计算机源程序, 源程序通过编译链接, 最后生成可执行程序
所以, 程序是一个算法具体的实现
复杂度
如何衡量一个算法的效率 ?
比如, 这段递归实现的斐波那契数列
long long Fib(int N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}程序是一个算法具体的实现，计算机运行程序时需要消耗时间资源和空间资源，所以衡量一个算法的好坏可以从时间和空间，这两个维度进行判断
时间，即时间复杂度，衡量一个程序运行所需要的时间。空间, 即空间复杂度，衡量一个程序运行所需要的额外空间
2. 时间复杂度
如何计算时间复杂度
在复杂度中写到，时间复杂度衡量一个程序运行所需要的时间。那么，计算时间复杂度就是数程序运行到结束所需要时间？
这种方法可行，但是有两个缺陷
1. 环境因素, 如果每次都需要上机写程序衡量一个算法，会很麻烦。
2. 机器因素, 两台不同配置的机器运行二个不同的算法，由于机器配置不同, 就不能比较两个算法的好坏
答案: 一个程序运行时间与执行语句的次数成正比例，计算执行语句的次数作为一个算法的时间复杂度
例子:
// 计算Func1中++count语句总共执行了多少次？
void 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 < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}++count 总共执行了 N2 + 2N + 10 次 ---> Func1执行N2 + 2N + 10 次语句
大O的渐进表示法
在计算语句执行次数时，是否需要计算到一个准确的数字？
不需要计算出一个准确的执行次数，只需要计算出执行语句属于哪一个量级, 这个量级用大O的渐进表示法描述
还是以Func1为例
// 计算Func1中++count语句总共执行了多少次？
void 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 < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}Func1执行N2 + 2N + 10 次语句 -----> O(N2)
当N为无穷大时, 2N+10对结果影响不大, 可以忽略不计 ---> N2 ---> 大O的渐进表示法描述 ---> O(N2) ---> Func1的时间复杂度为 O(N2)
计算时间复杂度的实例
// 计算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);
}执行2N+10次语句 ---> O(N) ---> Func2的时间复杂度为O(N)
当N为无穷大时, N前面的系数2可以忽略
// 计算Func3的时间复杂度
// N 远大于M
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);
}执行 N+M次语句, 因为N远大于M，所以M可以忽略不计， Func3的时间复杂度为 O(N)
// 计算Func4的时间复杂度
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}执行100次语句 ---> O(1) ---> Func4时间复杂度为 O(1)
当执行次数为常数次数时, 用1取代表示常数次
// 计算strchr的时间复杂度
const char* strchr(const char* str, int character)
{
while (*str)
{
if (*str == character)
{
return str;
}
else
{
str++;
}
}
}在字符串中查找一个字符, 找最坏的情况作为时间复杂度
最坏的情况是在找字符串中最后一个字符时找到 ---> O(N) ---> strchr的时间复杂度为 O(N)
这里的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])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}计算时间复杂度时，不能去数循环，应该看思想，比如这个冒泡排序
冒泡排序会这样执行:
[5 4 3 2 1]
4 3 2 1 5 ---> 执行N-1次
3 2 1 4 5 ---> 执行N-2次
................
1 2 3 4 5 ---> 执行1次
这是一个等差数列, 根据等差数列求和公式, 首项+尾项*项数/2 ---> N-1 + 1 * N / 2 = N2 / 2 ---> O(N2) ---> BubbleSort的时间复杂度为 O(N2)
// 计算BinarySearch的时间复杂度？
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为数组个数, x为查找次数, 最坏的情况是 n/2/2/2... = 1 ---> 2x = N ---> x = log2N
在这道题中, 查找次数可以等于语句执行的次数, 所以BinarySearch的时间复杂度为 O(log2N)
// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}语句执行的次数 = 递归的次数
Fac(N) -> Fac(N-1) -> Fac(N-2) -> .... -> Fac(0)
总共递归了N+1次 ---> Fac的时间复杂度为 O(N)
// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}语句执行的次数 = 递归的次数
2,4,8...这是一个等比数列 ---> Fib的时间复杂度为 O(2 N)
计算时间复杂度的总结
计算时间复杂度的关键是观察思想, 不能只看代码
其次，找到数据个数N与关键语句的关联
// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}这里的关键语句是 return Fac(N-1)*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])
{
Swap(&a[i-1], &a[i]);
exchange = 1;
}
}
if (exchange == 0)
break;
}
}这里的关键语句是整个第二层循环, 整个第二层循环决定最终程序的执行次数
最后根据数据个数N与关键语句之间的关系以及算法思想, 推导出属于哪个量级, 作为时间复杂度
