什么是算法？

算法：就是解决问题的方法或计算步骤。

学习算法的目的：采用不同的算法策略，设计高效率的程序。

算法的特征

1. 有穷性：算法的每个操作步骤都能在有限的时间内完成。
2. 确定性：每一步都必须有明确的定义，不允许有歧义性和多义性。
3. 输入：一个算法应该有0个或多个输入；
4. 输出：有一个或多个输出；
5. 可行性：每一个操作都应该是特定的解题规则中允许使用的、可执行的，并可以通过执行有限次来实现。

算法的评定

同一个问题，可用不同的算法来解决，而一个算法质量的优劣将影响程序的效率。 一个算法的评价主要从时间复杂度和空间复杂度来考虑。例如，计算 1 ~ n 之间整数和问题。

1. 时间复杂度 ：程序运行次数与问题规模(n)直接的关系。
2. 空间复杂度 ：算法需要消耗的内存空间。
3. 算法正确性 ：评价一个算法优劣的最重要的标准。
4. 算法可读性 ：算法可供人们阅读的容易程度。
5. 算法容错性 ：算法对不合理数据输入的反应能力和处理能力，也称为容错性。

如何计算程序执行时间？

最简单的思路，就是在程序开始时记录一下时间，结束时再记录一下时间，然后计算时间差。

#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;
int main() {
    struct timeval start, end;
    gettimeofday(&start, NULL);
    int cnt = 0;
    for(int i = 1; i <= 100000000; i++)
        cnt++;
    gettimeofday(&end, NULL);
    int t = 1000000 * (end.tv_sec - start.tv_sec) + end.tv_usec - start.tv_usec;
    t = t * 1.0 / 1000;
    printf("该程序用时%dms\n", t);
    return 0;
}

这种方式非常容易受运行环境的影响，在性能高的机器上跑出来的结果与在性能低的机器上跑的结果相差会很大。

如果机器性能差距很大，这种测评机制是不公平的。

那么，如何选择一种有效方案可以抛开机器性能差距，对不同算法效率进行评价呢？

大O表示法

通过大O符号表示法，这段代码的时间复杂度为 O(n) ，为什么呢？

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cout << i << " ";
    return 0;
}

在大O符号表示法中，时间复杂度的公式是： T(n)=O(f(n))

注：f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。

算法复杂度可以从最理想情况、平均情况和最坏情况三个角度来评估，由于平均情况大多和最坏情况持平，而且评估最坏情况也可以避免后顾之忧，因此一般情况下，我们设计算法时都要直接估算最坏情况的复杂度。

大O表示法具体如何表示呢？

比如某个算法的时间复杂度如下，其中n代表数据量。

常见时间复杂度

• 常数阶 O($1$) 没有循环或者循环只执行固定次
• 对数阶 O($\log{n}$) 有循环并且控制循环的变量以*2或者/2的方式出现
• 线性阶 O($n$) 单层循环
• 线性对数阶 O$(n\log{n})$
• 平方阶 O($n^2$) 循环嵌套
• 立方阶 O($n^3$)
• k次方阶 O($n^k$)
• 阶乘阶 O($n!$)

从上至下依次的时间复杂度越来越大，执行的效率越来越低。

[info] 啥是 log?

如果 $2^x=y$ 那么 $\log_2{y}=x$

可以简单理解为，“y 不停除以 2，最终变到 1” 需要的次数

$log_21024$=10

$log_22147483648=31$

常数阶O(1)

代码执行次数是一个常数，不随n的变化而变化，那这个代码的时间复杂度就都是O(1)，如下的代码中虽然含有for循环，但循环次数是100次，不随问题规模变化而变化，因此是常数级O(1)的时间复杂度：

int sum=0;
for(int i = 1; i <= 100; i++){    
    sum += i; 
}

线性阶O(n)

这段代码，for循环里面的代码会执行n遍，因此它消耗的时间是随着n的变化而变化的，因此这类代码都可以用O(n)来表示它的时间复杂度。

int sum=0;
for(int i = 1; i <= n; i++){
    sum += i;
}

对数阶O(log n)

同样是for循环，但这段代码的时间复杂度是O(log n)，因此不能单纯认为for循环就一定是O(n)的。

int cnt=0;
for(int i = 1; i <= n; i *= 2){
    cnt++;
}

在这个for循环里，i 开始是1，然后不是自增1，而是自乘2，因此i的值依次是1、2、4、8...... $2^x$ ，也就是当2的$x$次方大于n时，跳出循环，因此$x$ =log n， 程序执行了log n次，时间复杂度为：O(log n)

线性对数阶O(nlog n)

线性对数阶O(nlog n) 其实非常容易理解，将时间复杂度为O(log n) 的代码循环n遍的话，那么它的时间复杂度就是 nO(logn)。

for(int i = 1; i <= n; i++){    
    for(int j = 1; j <= n; j *= 2){    
        cnt++;
    }
}

平方阶$O(n^2)$

平方阶$O(n^2)$就更容易理解了，如果把$O(n)$的代码再嵌套循环一遍，它的时间复杂度就是 $O(n^2)$ 了。

for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
        cnt++;
    }
}

冒泡排序的时间复杂度也是$O(n^2)$,当i=1时，执行n-1次，i=2时，执行n-2次......因此总的执行次数也就是 (n-1)+(n-2)...+2+1就是n*(n-1)/2，显然$n^2$的量级更大，因此常数项和n/2可以忽略，时间复杂度即为$O(n^2)$：

for(int i =1; i<=n; i++){
    for(int j=1; j<=n-i; j++){
        if(a[j] > a[j+1]) 
            swap(a[j], a[j+1]);
    }
}

阶乘 O(n!)

比如用枚举的方法求1~n的全排列，时间复杂度是O(n!)，效率很低。