在單個鏈表上操作的大O

假設你有一個大小爲N的單鏈表，並且你想對每個元素執行一個操作，從最後開始。在單個鏈表上操作的大O

我已經想出以下僞代碼：

while N > 0 
    Current = LinkedList 
    for 0 to N 
     Current = Current.tail 
    end 
    Operation(Current.head) 
    N := N-1 
end

現在我必須確定哪些大O這種算法。
假設操作（）是O（1），我認爲這是這樣的：

N + (N-1) + (N-2) + ... + (N-(N-1)) + 1

但我不知道什麼大澳，實際上是。我認爲它肯定小於O（N^2），但我不認爲你可以說它的O（N）要麼...

來源

2011-01-23 fresskoma

1 + 2 + 3 + ... + N = N *（N + 1 ）/ 2這是O（n^2） – CodesInChaos 2011-01-23 19:42:22

我不太瞭解你的結構，你有LinkedList稱爲Current（它看起來像一個Node），它有尾部和頭部？如果你打算成爲prev/next，那麼它是雙重鏈接的;如果他們確實是頭/尾，上面的代碼根本就沒有意義。 – bestsss 2011-01-23 21:59:50

@bestsss：你可以說LinkedList是一個對象，每次我進入While循環時，我都會在Current中引用它。在Current（它是LinkedList）上調用「head」，返回實際的Element，而「tail」返回另一個LinkedList Object，包含，以及尾部... – fresskoma 2011-01-23 22:04:37

你的方程基本上是所述triangular numbers的，並且總計爲N（N + 1）/ 2。我會離開你去確定O()！

執行此操作的更快方法是構建與原始列表相反的新列表，然後對其執行操作。

來源

2011-01-23 19:42:36

你的算法是O（n^2）在你的文章中。但是，您可以在O（n）中執行此操作。

重要的是要記住Big-O符號是對算法時間複雜度的約束。

來源

2011-01-23 19:40:40

你的運行時分析是正確的，則運行時是1 + 2 + ... + N這是一個sum of the arithmetic progression因此=（N 2 - N）/ 2。

來源

2011-01-23 19:40:46 phihag

1+2+3+...+n = n*(n+1)/2 = 0.5 * N^2 + O（n）的

這是O（n^2），和爲O（n^2）是緊，即不存在下運行時以使要包含你的運行時。

更快的算法，從前面到後面的工作原理可以具有O（N），而不是爲O（n^2）

來源

2011-01-23 19:44:01 CodesInChaos

在單個鏈表上操作的大O

回答

相關問題