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 总共执行了 N² + 2N + 10 次 ---> Func1执行N² + 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执行N² + 2N + 10 次语句 -----> O(N²) 

当N为无穷大时, 2N+10对结果影响不大, 可以忽略不计 --->  N²  ---> 大O的渐进表示法描述 --->  O(N²)  ---> Func1的时间复杂度为  O(N²)

计算时间复杂度的实例

// 计算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
", 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
", 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
", 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 = N² / 2 ---> O(N²) ---> BubbleSort的时间复杂度为 O(N²)

// 计算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  --->  2^x = N --->  x = log₂N

在这道题中, 查找次数可以等于语句执行的次数, 所以BinarySearch的时间复杂度为 O(log₂N)

// 计算阶乘递归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与关键语句之间的关系以及算法思想, 推导出属于哪个量级, 作为时间复杂度