一. 时间复杂度
算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作
算法的效率是通过时间复杂度和空间复杂度来衡量的
时间复杂度用来定性描述该算法所用时间，空间复杂度用来定性描述该算法占用多少内存。
有时，时间和空间是【鱼和熊掌】的关系，不可兼得，这时通常牺牲空间换取时间，随着计算机硬件技术地不断发展，空间越来越不值钱，时间越来越值钱。
1.1 简介
想知道一个算法的运行时间，我们可能会想到把这个程序运行一遍。那么消耗的时间很容易求得。
但是这种方式非常容易受运行环境的影响
- 在性能高的机器上跑出来的结果与在性能低的机器上跑出来的结果相差很大
- 数据规模不一样，运行时间也不一样
- 程序必须运行，才能知道运行时间是多少
因此一种更为通用的方法被研究了出来：【大 O 符号表示法】。令数据规模为 n，则时间复杂度为 $O(f(n))$，$f(n)$ 表示每行代码的“执行次数之和”。
注意：大 O 是数量量级非常大下所表现出的时间复杂度，这个数据量，常数项系数已经不起决定性作用了，因此我们一般省略时间复杂度的常数项系数
复杂表达式的化简
$O(2n^2+10n+1000) \longrightarrow O(n^2)$
去掉加法常数项，因为常数项并不会因为 n 的增大而增加计算机的操作次数
去掉数量级小一级的 n，因为 n 平方的数据规模远大于 n
常见的时间复杂度量级有
- $O(1)$ 常数阶
- $O(logN)$ 对数阶
- $O(N)$ 线性阶
- $O(NlogN)$ 线性对数阶
- $O(N^2)$ 平方阶
- $O(N^3)$ 立方阶
- $O(N^k)$ k 次方阶
- $O(2^N)$ 指数阶
从上至下，时间复杂度越来越大，执行的效率越来越低
1.2 常数阶 O(1)
不论代码执行了多少行，只要没有循环等复杂结构，时间复杂度都是 O(1)
int num_1 = 1;
int num_2 = 2;
int num_3 = num_1 + num_2;
这个代码在执行的时候，消耗的时间并不随着某个变量的增长而增长，因此不论这类代码多长，即使有几万几十万行，都可以用 O(1) 来表示它的时间复杂度
1.3 线性阶 O(n)
for(int i = 0; i < size; ++i){
int res = i;
}
这个代码，for 循环里的代码会执行 size 遍，它消耗的时间是随着 size 的变化而变化，因此这类代码都可以用 O(n) 来表示它的时间复杂度
1.4 对数阶 O(logN)
int i = 1;
while(i < size){
i *= 2;
}
可以看出，程序执行会执行 $log_2 size$ 次，因此时间复杂度为 O(logN)
我们说某个算法的时间复杂度为 logN，那么一定是 log 以 2 为底 N 的对数吗？
不是的！！！，log 可以是以任意数为底 N 的对数，因此我们统一说 logN，即忽略底数的描述
为什么可以这么做呢？ $O(log_2 N)=O(log_2 10)*O(log_{10} N)$，而 $O(log_2 10)$ 是常数，在计算时间复杂度的时候可以忽略。
1.5 线性对数阶 O(NlogN)
将时间复杂度为 O(logN) 的代码循环执行 N 遍，那么它的时间复杂度就是 N * O(logN)，也就是 O(NlogN)
for(int i = 0; i < size; ++i){
int j = 1;
while(j < size){
j *= 2;
}
}
1.6 平方阶
将时间复杂度为 O(N) 的代码循环执行 N 遍，其实就是嵌套循环，它的时间复杂度就是 $O(N^2)$
for(int i = 0; i < size; ++i){
for(int j = 0; j < size; ++j){
char *str = "hello, world";
}
}
二. 空间复杂度
时间复杂度不是用来计算程序具体耗时，空间复杂度也不是用来计算程序实际占用多少内存
空间复杂度常见的有 $O(1)，O(N)，O(N^2)$
2.1 常数阶 O(1)
int num_1 = 1;
int num_2 = 2;
int num_3 = num_1 + num_2;
程序执行所需内存空间，不随某个变量 N 的大小而变化，因此空间复杂度为 O(1)
2.2 线性阶 O(N)
int *arr = (int*)calloc(size, sizeof(int));
这个代码，动态创建了一个数组，且数组大小随 size 的变化而变化，因此空间复杂度为 O(N)
作业
1. 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
示例1
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
你可以不使用额外空间来实现吗？