本文集是作者閱讀《算法圖解》一書所做的讀書筆記跛璧，內(nèi)容難免過于淺薄聘芜。之后將針對部分細節(jié)進行補充和完善，如有錯漏還望讀者留言指正侵浸。
算法是一組完成任務(wù)的指令，任何代碼片段都可視為算法氛谜。優(yōu)秀的算法可以提高程序執(zhí)行效率掏觉，或者解決一些有趣的問題。在學(xué)習(xí)算法的過程中我們可以嘗試理解算法的思路和應(yīng)用場景值漫，從而開闊視野澳腹，提升自身水準。
大O表示法
大O表示法是一種特殊的表示法杨何，用來表示算法處理數(shù)據(jù)花費的時間隨數(shù)據(jù)規(guī)模變化的規(guī)律酱塔，即算法的時間復(fù)雜度。
下面以簡單查找算法為例進一步了解算法復(fù)雜度的概念以及大O表示法的使用方法危虱。
public int search(int key, int[] arr) {
for (int idx = 0; idx < arr.length; idx++) {
if (key == arr[idx]) {
return idx;
}
}
return -1;
}
以上代碼實現(xiàn)了一個簡單的查找算法羊娃，search()方法接收兩個參數(shù)，key為要查找的目標埃跷，arr為查找的集合蕊玷，如果arr中包含該元素則返回元素的下標，否則返回-1弥雹。
假設(shè)檢查一個元素花費的時間為1垃帅，上面的算法當(dāng)中在最差的情況下需要檢查的次數(shù)為arr.length，平均檢查次數(shù)為1/2 * arr.length缅糟，所以上面查找算法查找元素花費的時間可以表示為t = 1/2 * arr.length挺智。使用大O表示法時通常會省略表達式中的常數(shù)項，所以簡單查找算法的時間復(fù)雜度為O(n)窗宦。
了解算法復(fù)雜度的意義在于：通過算法時間復(fù)雜度可以比較不同算法的操作數(shù)赦颇，計算算法運行時間隨數(shù)據(jù)規(guī)模的增速，從而評價算法的質(zhì)量赴涵。
常見的大O運行時間有以下幾種：
-
O(logN), 也叫對數(shù)時間媒怯。 -
O(N), 也叫線性時間。 - O(N*logN)髓窜。
- O(N2)扇苞。
- O(N!)欺殿。
下圖來自Time complexity - Wikipedia，圖中展示了常見算法復(fù)雜度的操作數(shù)隨輸入規(guī)模變化的曲線鳖敷。
至此引言部分結(jié)束脖苏，后續(xù)內(nèi)容將涉及常見排序算法，查找算法以及簡單的圖算法定踱。
作者水平有限棍潘，本文旨在記錄作者閱讀和學(xué)習(xí)過程，內(nèi)容質(zhì)量難以保證崖媚，暫不支持轉(zhuǎn)載亦歉，還望見諒
