--- title: 算法复杂度 url: 'https://yayi.site/archives/算法复杂度' cover: 'https://cdn.jsdelivr.net/gh/yan-bolan/picbed/img/动漫/結城友奈は勇者である/乃木·園子.png' abbrlink: 7db09267 date: 2020-11-02 10:50:38 updated: 2021-05-14 22:04:58 categories: tags: --- \[https://www.cnblogs.com/gaochundong/p/complexity_of_algorithms.html\](https://www.cnblogs.com/gaochundong/p/complexity_of_algorithms.html) 总之一般指的是算法的上界，也就是最坏的情况下。 θ O Ω 分别是 算法复杂度，上界，下界 复杂度一般有：常量 O(1)，对数，log~2~n 。线性 O(n) 。 平方 O(n^2^)。 立方，指数。 通常省略 常数。 ---- 二分法 复杂度： 第一次 剩下 n/2 第k 次 剩下 n/2^k^ 最坏情况 剩下 1 1= n/2^k^ 解得 k=log~2~n