关于时间复杂度
原来这么麻烦
有5种符号：
\(Θ：Θ(?(?))=\{?(?):∃?_1,?_2,?_0:∀?≥?_0:0≤?_1 ?(?)≤?(?)≤?_2 ?(?)\}\)
\(O：O(?(?))=\{?(?):∃?_1,?_0:∀?≥?_0:0≤?(?)≤?_1 ?(?)\}\)
\(Ω：Ω(?(?))=\{?(?):∃?_1, ?_0:∀?≥?_0:0≤?_1 ?(?)≤?(?)\}\)
\(o：o(?(?))=\{?(?):∃?_0:∀?_1>0,?≥?_0:0≤?(?)≤?_1 ?(?)\}\)
\(\omega ：\omega(?(?))=\{?(?):∃?_0:∀?_1>0,?≥?_0:0≤?_1 ?(?)≤?(?)\} \)
等号
\(?(?)=?(?(?))\),表示能从 \(?(?(?))\) 中可以选出一个函数 \(ℎ(?)\) 使得等号成立
传递性
\(?(?)=Θ(?(?))∧?(?)=Θ(ℎ(?))⇒?(?)=Θ(ℎ(?))\)
\(?(?)=O(?(?))∧?(?)=O(ℎ(?))⇒?(?)=O(ℎ(?))\)
\(?(?)=Ω(?(?))∧?(?)=Ω(ℎ(?))⇒?(?)=Ω(ℎ(?))\)
\(?(?)=o(?(?))∧?(?)=o(ℎ(?))⇒?(?)=o(ℎ(?))\)
\(?(?)=\omega (?(?))∧?(?)=\omega (ℎ(?))⇒?(?)=\omega (ℎ(?))\)
自反性
\(?(?)=Θ(?(?))\)
\(?(?)=Ω(?(?))\)
\(?(?)=Ο(?(?))\)
对称性
\(?(?)=Θ(?(?))⇔ ?(?)=Θ(?(?))\)
\(?(?)=?(?(?))⇔?(?)=Ω(?(?))\)
\(?(?)=?(?(?))⇔?(?)=\omega (?(?))\)
类比
\(Θ\) 的性质与 \(=\) 相同
\(O\) 的性质与 \(≤\) 相同
\(Ω\) 的性质与 \(≥\) 相同
\(o\) 的性质与 \(<\) 相同
\(\omega\) 的性质与 \(>\) 相同
思考：\(n\) 与 \(n^{1+\sin n}\) 能够比较吗
分治
将大小为 \(n\) 的问题分为 \(a\) 个 大小为 \(\frac{n}{b}\) 的子问题，然后合并
归并排序 \(T(n)=2T(\frac{n}{2})+O(n)\)
主定理
Top K
