線(xiàn)性復(fù)雜度計(jì)算公式？

公式 :O(N) + O(K) + O(N)*O(1) = O(N + K) 。計(jì)數(shù)排序，輸入 n 個(gè)范圍在 0-k 區(qū)間的元素，當(dāng) !k >> n 時(shí)，排序的運(yùn)行時(shí)間為 O(N)

論點(diǎn)：對(duì)于輸入的任一的元素 x，如果有 s 個(gè)元素小于，則元素 x 就可以放在 s+1 的位置上，這個(gè)時(shí)間復(fù)雜度近乎 O(1)，我們僅需要得出對(duì)于每個(gè)元素有多少個(gè)小于的元素的列表即可在很短的時(shí)間內(nèi)排序完成。

a.對(duì)原數(shù)組進(jìn)行遍歷，計(jì)算每個(gè)元素出現(xiàn)的次數(shù)，時(shí)間復(fù)雜度 O(N)，空間復(fù)雜度 O(K)