最近復習到資料結構，總結一下之前一直沒懂的最壞，最好，平均情況的時間復雜度
最好：
每次要查找的資料剛好在資料的第一個，即每個數只要查一次就可以了，帶入O表示為O（1）
最壞：
每次要查找的資料剛好在資料的最后一個，即第一個數要查n次，第二個要查n-1次，第三個要查n-2次。。。以此類推，最后一個要查一次即可，累加一下就是（1+n）n/2。即每個數平均下來要查找（1+n）/2次，帶入O表示為O（n）。
平均（即加權平均）：
這個之前一直沒看懂，現在簡單總結一下。假如陣列有n個位置，每個位置剛好是你要查的資料的概率為1/（1+n），（n個資料有n種，再加一是所查的數不在資料中的情況）。
接下來就看查一個數，每個位置要查幾次，顯然，第一個位置要查1次到達，第二個位置查2次到達，第三個位置查3次到達。。。。。第n個位置查n次到達，總共就是1+2+3+。。。+n
即每個數平均下來要查找1/(1+n) * (1+2+3+....n) 即書本上的n（n+3）/2（n+1）。帶入O，去掉低階項為O（n）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/19419.html
標籤：新技術前沿
上一篇：資料庫+java