Linearsort - 運行時分析

首先，非常感謝發佈在我的問題主題中的每個人，你們都給了我很多幫助，並且非常有趣，無論是詢問還是閱讀答案，並改進我的工作。Linearsort - 運行時分析

...................

- 依託n和m，這將是以下算法的運行時間？我不知道價值n或m所以我只會說它是非常大的:) 然而，我不太明白什麼「< - 」代表哪個是解決任務的大問題。

但我試了一下：當我們說n是非常大的東西，那麼整個陣列arr將是非常大的。到目前爲止，我們得到了一個運行時間O(n)，這將需要運行數組arr，同樣適用於其他陣列，所以我們仍然在O(n)。每個for循環也將花費O(n)，所以我們將以O(n+x)結束，其中x是大整數，與數組arr大小一樣大。你可以看到我跳過了得到「< - 」的部分，因爲我真的不知道如何理解它。但是在我看來，總的運行時間將會是O(n)，對嗎？

Input: Array arr with n integers, from 1 to m 
Output: Array arr sorted upwards 

Initialize Array B with length m which is set to 0 everywhere 
n <-- |arr| 
Initialize Array C with length n 
for i = 1 to n do 
    B[arr[i] <-- B[arr[i]] + 1 
end for 
for j = 2 to m do 
    B[j] <-- B[j] + B[j-1] 
end for 
for i = n down to 1 do 
    C[B[arr[i]]] <-- arr[i] 
    B[arr[i]] <-- B[arr[i]] - 1 
end for 
return C

來源

2016-06-12 itaminul

'< - '被分配和這個算法被計數分類 – harold

謝謝！我首先以爲這是Insertionsort，但後來在for循環中實現了for循環：D – itaminul

因此該算法的運行時間爲O（2 * N + M）=> O（N + M），所以它是線性

來源

2016-06-12 18:39:05 Thomas

O（2 * n + m），爲什麼2 * n？我想因爲數組arr和「初始化長度爲n的數組C」，對嗎？ – itaminul

你有2次for循環從1到n（或n到1），所以你有2 * n ...但2 *是一個穩定的因子，所以你可以忽略它並將其計爲O（n） – Thomas

真棒謝謝你！我明白:)） – itaminul

Linearsort - 運行時分析

回答

相關問題