前言

算法是什么？我们如何来评估算法的好坏？有没有一种优美的数学方式来评估算法好坏，而不受客观环境的影响。例如计算机的性能影响？

学习此部分，需要掌握一定的C语言基础

本部分内容参考程杰老师《大话数据结构》，青岛大学王卓老师的授课等综合个人所学的总结笔记

本篇写于时间，部分内容可能与现在不符，请自行判断

——这一招是我从我最爱的游戏里学来的♬

算法的定义

算法是解决特定问题求解步骤的描述，在计算机中表示为指令的有限序列并且每条指令表示一个或者多个操作
算法通俗理解就是对于问题的特定解决步骤。

算法的特性

输入输出
算法具有零个或者多个输入，至少有一个输出。
有穷性
算法在有限的步骤之后，能够自动结束而非无限循环。
确定性
算法的每一个步骤都具有确定的含义，不会存在二义性。
可行性
算法的每一个步骤都必须是可行的，也就是说每一步，都能执行有限次数完成。

算法设计要求

正确性
算法的正确性是指算法至少应该具有输入，输出和加工处理无歧义性，能正确的反映问题的需求，能够得到问题的正确答案。
可读性
算法设计的另一目的是为了便于阅读，理解和交流
健壮性
当输入的数据不合法时，算法也可以对其做出相应处理，而不是产生异常或者奇怪的结果
时间效率高和存储量低
即最大限度的提升算法消耗的时间和资源占用度

算法效率的度量方法

如何来评估一个算法的效率和好坏？可以通过两种方法来分析：

事后统计方法
就是对于不同算法来使用同一计算机运行，结束后统计算法耗时
事前分析估算法
在计算机编制前，依据统计方法对算法的进行评估

经过分析发现，一个高级语言编写的程序在计算机上运行时所消耗的时间取决于以下因素：

算法采用的策略，方法；
编译产生的代码的质量；
问题的输入规模
机器执行指令的速度

对于第一条来说就算法好坏的根本，剩下的都需要看外部环境，也就是说抛开计算机硬件和软件的环境因素，一个软件的运行时间，依赖于算法的好坏和问题的输入规模。

下面举例一个算法，求和 $1+2+3+4+…+100$ 的和

第一种算法：

int i, sum = 0, n = 100;    //执行了一次
for (i=1; i <= n; i++)  //执行了n+1次
{
    sum = sum + i;  //执行了n次
}
printf("%d", sum);  //执行了1次

第二种算法：

1
2
3

int sum = 0, n = 100;   //执行了1次
sum = (1 + n) * n / 2;  //执行了1次
printf("%d", sum);  //执行了1次

显然第一种算法执行了 $1+(n+1)+n+1$次 $=2n+3$ 次；而第二种算法执行了 $1+1+1=3$ 次。实际上两个算法的第一句和最后一句是一样的，所以我们只需要关心中间部分。如果我们把循环堪称一个整体，忽略判断的执行次数，那么对于两个算法执行了 n 次还是 1 次的差距，算法的好坏就一目了然了。

再来延申一下这个例子：

int i, j, x = 0, sum = 0, n = 100;  //执行1次
for (i = 1; j <= n; i++)
{
    for (j = 1; j <= n; j++)
    {
        x++;    //执行nxn次
        sum = sum + x;
    }
}
printf("%d", sum);  //执行1次

对于这个例子来说，算法需要执行 $n^2$ 次，算法的效率也远差于上面的两个例子。

此时就可以得出，测试运行时间最可靠的方法解释计算对运行时间消耗的基本操作的执行次数。

这样就引出了我们的算法的时间复杂度。

算法的时间复杂度

算法时间复杂度的定义

在进行算法分析时，语句总的执行次数 $T(n)$ 是关于问题规模 $n$ 的函数，进而分析 $T(n)$ 随 $n$ 的变化情况并确定 $T(n)$ 的数量级。算法的时间复杂度，也就是算法的时间量度，记作：$T(n)=O(f(n))$。它表示随问题规模 $n$ 的增大，算法执行时间的增长率和 $f(n)$ 的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中 $f(n)$ 是问题规模 $n$ 的某个函数。

这样用大写 $O()$ 来体现算法时间复杂度的记法，我们称之为大O记法。

一般情况下，随着 $n$ 增大， $T(n)$ 增长最慢的算法为最优算法。

推导大 $O$ 阶方法

推导大 $O$ 阶的基本方法：

用常数1取代运行时间中的所有加法常数
在修改后的运行次数函数中，只保留最高阶项
如果最高阶项存在且不是1，则去除与这个项相乘的常数。
最终得到的结果就是大 $O$ 阶

常数阶

对于一开始第二种算法的时间复杂度来说

1
2
3

int sum = 0, n = 100;   //执行了1次
sum = (1 + n) * n / 2;  //执行了1次
printf("%d", sum);  //执行了1次

这个算法的运行次数是 $f(n)=3$ 。根据大 $O$ 推导法，不含最高阶，常数项用1取代，所以该算法的时间复杂度为 $O(1)$

同理，类比下面的算法

int sum = 0, n = 100;   //执行了1次
sum = (1 + n) * n / 2;  //执行了1次
sum = (1 + n) * n / 2;  //执行了1次
sum = (1 + n) * n / 2;  //执行了1次
sum = (1 + n) * n / 2;  //执行了1次
sum = (1 + n) * n / 2;  //执行了1次
sum = (1 + n) * n / 2;  //执行了1次
sum = (1 + n) * n / 2;  //执行了1次
printf("%d", sum);  //执行了1次

不论 $n$ 的值为多少，只要是常数项，一律时间复杂度为 $O(1)$ ，我们称这种时间复杂度为常数阶

对于单纯的分支结构，它的执行次数是固定的，不会随着 $n$ 的次数增大而变化，对于分支结构的时间复杂度也为常数阶，即 $O(1)$

线性阶

线性阶的循环结构会有些复杂。一般情况下，首要去分析循环结构的运行情况来分析算法的复杂度。
例如,下面的代码，它的循环时间复杂度为 $O(n)$ ,因为在循环体中代码需要执行 $n$ 次。

int i;
for (i = 0; i < n; i++)
{
    /* 时间复杂度为O(1)的步骤 */
}

对数阶

如下经典的例子：

int count = 1;
while (count<n)
{
    count = count * 2;
}

由于每次循环都乘2，所以循环 $x$ 次后，$2^x=n$ ,转换一下就是 $x=log_2n$，则会退出循环，所以该段代码的复杂度为 $O(log_2n)$

平方阶

下面是一个嵌套循环

for (int i = 0; i < n; i++)
{
    for (int j = 0; i < n; j++)
    {
        /* 时间复杂度为O(1)的步骤 */
    }
}

每一个嵌套循环次数为 $n$ ，嵌套后整体的算法复杂度为 $O(n^2)$
如果外层嵌套循环次数改为了 $m$，那么时间复杂度则为 $O(m \times n)$

for (int i = 0; i < n; i++)
{
    for (int j = 0; i < m; j++)
    {
        /* 时间复杂度为O(1)的步骤 */
    }
}

由此可以得出，对于嵌套循环来说，时间复杂度为 $外层循环次数 \times 嵌套循环次数$ 。

那么对于下面的代码

for (int i = 0; i < n; i++)
{
    for (int j = i; i < n; j++)
    {
        /* 时间复杂度为O(1)的步骤 */
    }
}

根据嵌套关系可知：总的执行次数为: $n+(n-1)+(n-2)+(n-3)+…+1 =\frac{n(n+1)}{2}=\frac{n^2}{2}+\frac{n}{2}$

不理解的详情查询数学《等差数列》

根据时间复杂度大 $O$ 阶的表示方法，保留最高项，去除最高项常数，所以最终的时间复杂度为：$O(n^2)$。
一般的代码时间复杂度大概说明了，那么对于方法的时间复杂度怎么计算？例如：

int i, j;
void function(int count)
{
    printf(count);
}
for ( i = 0; i < n; i++)
{
    function(i);
}

这段代码的$执行次数=代码部分+方法部分$，方法的执行次数为$1$，那么总的时间复杂度为$O(n)$。
那么对于下面的代码来说，时间复杂度则同上面的例子

int i;
void function(int count)
{
    int j;
    for (j = count; i < n; i++)
    {
        /* 时间复杂度为1的代码 */
    }
}
for ( i = 0; i < n; i++)
{
    function(i);
}

时间复杂度为：$O(n^2)$。

常见的时间复杂度

常见的时间复杂度如下表所示：

执行次数函数	阶	非正式术语
$12$	$O(1)$	常数阶
$2n+3$	$O(n)$	线性阶
$3n^2+2n+1$	$O(n^2)$	平方阶
$5log_2n+20$	$O(log_2n)$	对数阶
$2n+3nlog_2n+19$	$O(nlog_2n)$	$nlog_2n$阶
$6n^3+2n^2+3n+4$	$O(n^3)$	立方阶
$2^n$	$O(x^n)$	指数阶
常用的时间复杂度所耗时从小到大的排序：
$$O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n^3)<O(2^n)<O(n!)<O(n^n)$$
对于时间复杂度在 $O(n^3)$ 之后的时间复杂度，随着 $n$ 的增大，所耗时是指数级增大。