# 时间复杂度

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) 𝑂(1)O(1) 常数阶
𝑂(log𝑛)O(log⁡n) 对数阶
𝑂(𝑛)O(n) 线性阶
𝑂(𝑛log𝑛)O(nlog⁡n) 线性对数阶
𝑂(𝑛2)O(n2) 平方阶
𝑂(𝑛3)O(n3) 立方阶
𝑂(𝑛𝑘)O(nk) 𝑘k次方阶（𝑘>3k>3𝑘𝑍k∈Z
𝑂(2𝑛)O(2n) 指数阶 ## O(nlogn)

$O(logn)$的算法复杂度，典型的比如二分查找。设想一堆试卷，已经从高到底按照分数排列了，我们现在想找到有没有 59 分的试卷。怎么办呢？先翻到中间，把试卷堆由中间分成上下两堆，看中间这份是大于还是小于 59，如果大于，就留下上面那堆，别的丢掉，如果小于，就留下下面那堆，丢掉上面。然后按照同样的方法，每次丢一半的试卷，直到丢无可丢为止。

$$\frac{n}{2^k} = 1\Rightarrow k = log_2 n$$

### 觉得文章有用就打赏一下文章作者

#### 支付宝扫一扫打赏 #### 微信扫一扫打赏 • QQ咨询
• 回顶
{"ft_lang_label":"__label__zh","ft_lang_prob":0.96656245,"math_prob":0.9984959,"size":2081,"snap":"2021-43-2021-49","text_gpt3_token_len":2028,"char_repetition_ratio":0.08521906,"word_repetition_ratio":0.0,"special_character_ratio":0.28976452,"punctuation_ratio":0.0028490028,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9926272,"pos_list":[0,1,2,3,4,5,6,7,8,9,10],"im_url_duplicate_count":[null,2,null,2,null,2,null,null,null,null,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-10-21T14:56:46Z\",\"WARC-Record-ID\":\"<urn:uuid:9f1673e9-d09b-4d7b-be84-2e17e6a6a0f4>\",\"Content-Length\":\"81599\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:bf056a37-7493-44d9-9813-963d41e50164>\",\"WARC-Concurrent-To\":\"<urn:uuid:cf1071b7-36e7-497d-945f-c3220f053754>\",\"WARC-IP-Address\":\"173.82.120.127\",\"WARC-Target-URI\":\"https://www.ithothub.com/arithmetic/2021070418174344.html\",\"WARC-Payload-Digest\":\"sha1:4OIYV4UE3VQFCHSP7YVFM3VF3Y4KGLMP\",\"WARC-Block-Digest\":\"sha1:F4PFALPOAMPRQZ6ESEOU6TGBWEJPDN6U\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-43/CC-MAIN-2021-43_segments_1634323585424.97_warc_CC-MAIN-20211021133500-20211021163500-00194.warc.gz\"}"}