算法圖解筆記 - 算法簡介

算法圖解筆記

• • 算法簡介

    二分查找

    數組和連結清單的操作的運作時間

    操作	數組	連結清單
    讀取	O(1)	O(n)
    插入
    删除

    選擇排序

    将一組數按照從大到小的順序排序

    算法運作時間

    O(n*1/2*n)

    ，但大O表示法省略諸如1/2這樣的常數，是以簡單的寫作

    O(n*n)

    數組和連結清單總結

    • 計算機記憶體猶如一大堆抽屜
    • 需要存儲多個元素時，可使用數組或連結清單
    • 數組的元素都在一起
    • 連結清單的元素時分開的，其中每個元素都存儲了下一個元素的位址
    • 數組的讀取速度很快
    • 連結清單的插入和删除速度很快
    • 在同一個數組中，所有元素的類型都必須（都為int或doubl
    • O(log n)，也叫對數時間，這樣的算法包括二分查找。
    • O(n)，也叫線性時間，這樣的算法包括簡單查找。
    • 二分查找到速度比簡單查找快得多
    • O(log n)比O(n)快。需要搜尋的元素越多，前者比後者就快得越多
    • 算法運作時間并不以秒為機關
    • 算法運作時間是從其增速的角度度量的
    • 算法運作時間用大O表示法表示