靚麗時尚館

位置:首頁 > 健康生活 > 心理

線性複雜度計算公式

心理2.5W
線性複雜度計算公式

公式   :O(N) + O(K) + O(N)*O(1) = O(N + K)  。計數排序,輸入 n 個範圍在 0-k 區間的元素,當 !k >> n 時,排序的執行時間為 O(N)

論點:對於輸入的任一的元素 x,如果有 s 個元素小於,則元素 x 就可以放在 s+1 的位置上,這個時間複雜度近乎 O(1),我們僅需要得出對於每個元素有多少個小於的元素的列表即可在很短的時間內排序完成。

a.對原陣列進行遍歷,計算每個元素出現的次數,時間複雜度 O(N),空間複雜度 O(K)

標籤:複雜度 線性