一、簡(jiǎn)介
表示時(shí)間的大O符號(hào)，是用來描述算法效率的語(yǔ)言和度量單位蟀给。
大O表示法分析了算法的運(yùn)行時(shí)間如何隨列表的增長(zhǎng)而增長(zhǎng)捞高，指出了算法最糟情況下的運(yùn)行時(shí)間。
二乘综、大O表示法
n為列表的長(zhǎng)度，（n）作為大O表示法的操作數(shù)。
注：
1忍饰、算法的運(yùn)算速度指的并非時(shí)間，而是操作數(shù)的增速寺庄。
2艾蓝、談?wù)撍惴ǖ乃俣葧r(shí)，我們說的是隨著輸入的增加斗塘，其運(yùn)行時(shí)間將以什么樣的速度增加赢织。
三、常見的大O運(yùn)算時(shí)間
- O（log n）馍盟，也叫對(duì)數(shù)時(shí)間于置，這樣的算法包括二分查找。
- O（n）贞岭，也叫線性時(shí)間八毯，這樣的算法包括簡(jiǎn)單查找。
- O（n * log n）瞄桨，這樣的算法包括快速排序话速。
- O（log n2），這樣的算法包括選擇排序芯侥。
- O（log n!）泊交，旅行商問題解決方案的一種算法，一種非常慢的算法。
四活合、關(guān)于常量
大O表示法通常不考慮常量雏婶，因?yàn)槿绻@兩種算法的大O運(yùn)行時(shí)間不同，這個(gè)常量將無關(guān)要緊白指。
大O表示法不考慮乘以留晚、除以、加上或減去的數(shù)字告嘲。如O(n+26)错维、O(n-26)、O(n*26)橄唬、O(n/26)赋焕，它們都應(yīng)該表示為O(n)。
如下圖：
其中Ο(log2n )仰楚、Ο(n)隆判、 Ο(nlog2n )、Ο(n2)和Ο(n3)稱為多項(xiàng)式時(shí)間僧界，而Ο( 2n)和Ο(n!)稱為指數(shù)時(shí)間侨嘀。計(jì)算機(jī)科學(xué)家普遍認(rèn)為前者（即多項(xiàng)式時(shí)間復(fù)雜度的算法）是有效算法，把這類問題稱為P（Polynomial,多項(xiàng)式）類問題捂襟，而把后者（即指數(shù)時(shí)間復(fù)雜度的算法）稱為NP（Non-Deterministic Polynomial,非確定多項(xiàng)式）問題咬腕。
參考
1、《算法圖解》https://www.manning.com/books/grokking-algorithms
2葬荷、《算法的基本概念》https://www.zybuluo.com/defias/note/286416
