大 O 表示法是一種特殊的表示法绍移，指出了算法的速度有多快环凿。
在我們的日常工作中集嵌，基本都是使用其他人編寫好的算法萝挤，基本不太在乎算法的速度到底有多快。
但是根欧，人要往高處走嘛~最重要的是怜珍，面試的時(shí)候，面試官肯能會問...
那么我們今天來簡單的了解一下 大 O 表示法 凤粗。
- 大O表示法 是什么樣子酥泛？
指出了算法需要執(zhí)行的操作數(shù)。之所以叫大O表示法就是因?yàn)椴僮鲾?shù)前有一個(gè)大O嫌拣，就是這么隨意...
舉個(gè)栗子
假設(shè)有一個(gè)數(shù)組柔袁，包含了n個(gè)元素。簡單查找异逐，也就是從數(shù)組的第0項(xiàng)（索引項(xiàng)）找到某個(gè)元素捶索，需要從頭檢查到尾，因此需要執(zhí)行 n 次操作灰瞻。使用大O表示法腥例，這個(gè)運(yùn)行時(shí)間為 O(n)。單位呢酝润？沒有--大O表示法指的并非以秒為單位的速度燎竖。大O表示法讓你能夠比較操作數(shù)，它指出了算法運(yùn)行時(shí)間的增速袍祖。
再比如底瓣，為了檢查長度為 n 的數(shù)組谢揪，二分查找法需要執(zhí)行l(wèi)ogn次操作蕉陋。使用大O表示法就是 O(logn) 捐凭。大O表示法指出了最糟糕情況下的運(yùn)行時(shí)間
假設(shè)有一個(gè)數(shù)組[1,2,3,4,5]，如果使用簡單查找要查找“1”的話凳鬓，一次就能找到茁肠，但是即使這樣，算法的運(yùn)行時(shí)間依舊是O(n)而不是O(1)缩举。-
常見的大O運(yùn)行時(shí)間
- O(log n) 也叫對數(shù)時(shí)間垦梆，這樣是算法包括二分查找法
- O(n) 也叫線性時(shí)間，這樣的算法包括簡單查找
- O(n*log n) 這樣是算法包括快速排序--一種比較快的排序算法
- O(n2) 這樣的算法包括選擇排序--一種比較慢的排序算法
- O(n!) 這樣的算法包括旅行商問題的解決方案--一種非常慢的算法
畫個(gè)圖
假設(shè)要畫一個(gè)包含16格的網(wǎng)格(4*4)仅孩，且有以上5種不同的算法可供選擇托猩，使用第一種算法的時(shí)候操作數(shù)為4（log6=4），假設(shè)每秒可執(zhí)行10次操作辽慕，那么需要0.4秒即可京腥。那么如果要畫1024個(gè)格子呢？這需要執(zhí)行10次（log1024=10）溅蛉，也就是一秒就可以畫完了。
下圖分別畫出了繪制16個(gè)格子、繪制256個(gè)格子和繪制1024個(gè)格子在五種算法中分別消耗的時(shí)間奴愉。（這個(gè)例子是一個(gè)簡化比較版本职辨，實(shí)際情況可能個(gè)那個(gè)復(fù)雜）
大O表示法可以幫助我們快速分析算法的性能優(yōu)劣，也可以幫助我們分析一個(gè)算法的實(shí)用性镜撩。
