Time Complexity - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

小学生也能看懂的时间复杂度（大概吧）
时间复杂度和空间复杂度，大O表示法【数据结构和算法入门2】

渐近符号 Asymptotic Notation
算法导论------递归算法的时间复杂度求解
何为多项式地大于（小于）
【计算机科学】如何计算时间复杂度(Recursion tree & Master method)
巧用公式法快速求解时间复杂度
所有的递归算法空间复杂度都是O(n)吗?

定义：若存在一个常数c > 0和n0 > 0，对于任意的n > n0，使得T(n) <= cf(n)，则可得到T(n) = O(f(n))

T(n)	f(n)	big-O
T(n) = 1000n	f(n) = n	T(n) = O(n)
T(n) = 1000n	f(n) = n^2	T(n) = O(n^2)
T(n) = n^2	f(n) = n	T(n) ≠ O(n)
T(n) = 13n^2 + n	f(n) = n^2	T(n) = O(^2)

定义：若存在一个常数c > 0和n0 > 0，对于任意的n > n0，使得T(n) >= cf(n)，则可得到T(n) = Ω(f(n))

T(n)	big-Ω
T(n) = 1000n	T(n) = Ω(1)
T(n) = n	T(n) = Ω(n)
T(n) = n^2	T(n) = Ω(n)
T(n) = 13n^2 + n	T(n) = Ω(n^2)

定义：当且仅当T(n) = O(f(n))和T(n) = Ω(f(n))，可得T(n) = θ(f(n))

T(n)	big-θ
T(n) = 1000n	T(n) = θ(n)
T(n) = n	T(n) ≠ θ(1)
T(n) = n^2	T(n) = θ(n^2)
T(n) = 13n^3	T(n) ≠ Ω(n^2)

T(1) = 1
T(n) = 3T(n/3) + 3n

T(n/2) = 3^2 * T(n/3^2) + 3 * 2n = 9T(n/9) + 6n
T(n/2) = 3^3 * T(n/3^3) + 3 * 3n = 27T(n/27) + 9n
...
T(n) = 3^k * T(n/3^k) + 3kn

设 n = 3^k
得 k = log3n (3是底数)
T(n) = n * T(1) + 3log3n * n
T(n) = n * (1 + 3log3n)

T(n) = O(nlogn)

主定理（Master Theorem）与时间复杂度
主定理 Master Theorem
Master—Theorem 主定理的证明和使用

• 解析1
  
• 解析2

	Array速度最快（理论上没有区别，但是经验所得）	Linked List	Red-black Tree
扫描全部数据	O(n)	O(n)	O(n)
搜索	二分搜索O(logn)	O(n)	O(logn)

传统方法：

运行textFile = textFile + c时

1. 创建一个临时字符串
2. 复制textFile到新的字符串（复制k个字符的字符串要O(k)）
3. 把c添加到字符串
4. 重新分配textFile的指针指向新的字符串

具体的时间复杂度为：1 + 2 + 3 + 4 + 5 + ... + n = n(n + 2)/2 = O(n^2)

改进方法：（用数组装字符）

• 若T(n)是一个k次多项式，可得T(n) = O(n^k)
• 若T(n) = O(f(n))和S(n) = O(g(n))，可得T(n) + S(n) = O(f(n) + g(n))
• 若T(n) = O(f(n))和S(n) = O(g(n))，可得T(n) * S(n) = O(f(n) * g(n))
• log(n!) = O(nlogn)