Time & Space Complexity
A. Time Complexity
1. E.g.:
for (int i = 1; i <=n; ++i) { // Do (n + 1)
for (int j = 1; j <= n; ++j) { // Do n(n + 1)
x = x + 1; // Do n^2
}
}
执行次数： (n + 1) + n(n + 1) + n² = f (n) = 2n²+ 2n + 1
算法执行时间： T(n) = O(n²) ==> 一般取最高次
<==> 随问题规模 n 提升， T(n) ∝ n²
2. Definition
Time Complexity： T(n) = O(f (n)) <=> 当 n 够大时， T(n) ∝ f (n) => { f (n) : 执行次数 }
大 O 记法:
O(1) : 常量型，效率高
O(n)：线性型
O(n²)，O(n³)
O(log n)，O(nlog n)
O(2ⁿ)
O(1) < O(log n) < O(n) < O(nlog n) < O(n²) < O(n³) < O(2ⁿ)
3. Tips
随 n 变大， f (n) 增长慢的更优
4. 常见时间复杂度表示
B. Space Complexity -- 算法占用空间
1. E.g. :
for (int i = 1; i <=n; ++i) { // Do (n + 1)
for (int j = 1; j <= n; ++j) { // Do n(n + 1)
x = x + 1; // Do n^2
}
}
T(n) = O(n²)
S(n) = O(1)
f[0] = 0;
f[1] = 1;
for (int j = 2; j <= n; ++j) {
f[j] = f[j - 1] + f[j - 2];
}
T(n) = O(n)
S(n) = O(n)
2. Definition
空间复杂度是一个算法在运行过程中临时占用存储空间大小的量度。
算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作:S(n)= O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。
若输入数据所占空间只取决于问题本身，和算法无关，这样只需要分析该算法在实现时所需的辅助单元即可。算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称此算法为原地工作，空间复杂度为0(1)。
通常只说“复杂度”的时候指的是空间复杂度。
3. Tips
经验
复杂度与时间效率的关系：
c(常数) < logn < n < n*logn < n^2 < n^3 < 2^n < 3^n < n!
l------------------------------l-----------------------------------l--------l
较好 一般 较差
常用算法的时间与空间复杂度
