什么是算法？

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

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

算法的特征

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

算法的评定

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

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

如何计算程序执行时间？

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

#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$

时间复杂度和空间复杂度