大哦（n日誌n）

我目前正在研究大哦的基本算法。我想知道是否任何人都可以告訴我使用Big Oh的Java代碼（n log n）會是什麼樣的，或者指示我到哪裏存在的SO頁面。大哦（n日誌n）

由於我只是一個初學者，我只能在編寫代碼之前想象它的代碼。因此，理論上（至少），它應該包含一個for循環，我們有n次。然後對於日誌n，我們可以使用while循環。所以然後循環執行n次，while循環執行log base 2次。至少我是這麼想的，但是看到代碼能夠解決問題。

來源

2013-09-26 hherklj kljkljklj

我不知道我是否正確理解你。你是否要求一個在O（n log n）中具有時間複雜度的算法的例子？ – Carsten

嘗試研究合併排序等任何良好的排序算法。以下鏈接可能會幫助您http://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities –

是的。我只想看看代碼在Java程序中的樣子。 –

非常流行的O（n log n）算法是合併排序。 http://en.wikipedia.org/wiki/Merge_sort例如算法和僞代碼。算法的log n部分是通過將問題分解爲更小的子問題來實現的，其中遞歸樹的高度爲log n。

很多排序algortihms的運行時間爲O（n log n）。更多示例請參閱http://en.wikipedia.org/wiki/Sorting_algorithm。

來源

2013-09-26 06:48:42 rcs

http://en.wikipedia.org/wiki/Heapsort

簡單的例子是，就像你描述的 - 執行n次一些的操作，需要的log（n）時間。平衡二叉樹具有log（n）高度，所以一些樹算法會具有這樣的複雜度。

來源

2013-09-26 06:49:35 mabn

int n = 100 
for(int i = 0; i < n; i++) //this loop is executed n times, so O(n) 
{ 
    for(int j = n; j > 0; j/=2) //this loop is executed O(log n) times 
    { 

    } 
}

說明：外循環應清楚。它執行n次。現在到內部循環。在內部循環中，你只需要n並且總是將它除以2。所以你問自己：我可以用2來劃分n多少次。事實證明這是O (log n)。（實際上日誌的基礎是2，但是在Big-Oh表示法中，我們離開了基地，因爲它只會將一些因素添加到我們不感興趣的日誌中）。

所以你正在執行一個循環n次，並在該循環內執行另一個循環log(n)次所以你有O(n) * O(log n) = O(n log n)。

來源

2013-09-26 06:52:17 slashburn

這將是O（n日誌n），但它是不現實的。幾乎所有* O（n log n）算法都是遞歸的。也許你可以提供一個更典型的形式。 –

本示例旨在提供有關O（n log n）是什麼的非常簡單的示例。實際上你不會看到這種算法。是的，這些算法是遞歸的，但反覆解釋O（n log n）更容易理解。關鍵是要看到你總是把n除以2。這是大多數算法中的一個關鍵特性，比如Mergesort，每個半部分都使用相同的算法。我認爲這是合適的，因爲他在他的問題中討論了嵌套循環。 – slashburn

@slashburn謝謝，這是最簡單的解釋..！ – TheFlash

具有O(.)時間複雜度的算法涉及log n通常涉及某種形式的分而治之。

例如，在MergeSort列表中減半，每個部分單獨合併排序，然後將這兩部分合並在一起。每個清單是減半。

每當您將工作量減半或減少一定的固定係數時，通常最終會得到O(.)的log n組件。

就代碼而言，請查看MergeSort的算法。典型實現的重要特徵是它是遞歸的（請注意，TopDownSplitMerge在維基百科給出的代碼中調用了兩次）。

所有優秀的標準排序算法都具有時間複雜度O(n log n)，在最糟糕的情況下不可能做得更好，請參閱Comparison Sort。

要查看Java代碼中的外觀，只需search！ Here's one example。

來源

2013-09-26 06:53:49

大哦（n日誌n）

回答

相關問題