如何有效計算算法的時間複雜度？

我正在研究算法的複雜性，我仍然無法確定一些算法的複雜性......好吧，我能夠找出基本的O（N）和O（N^2）循環，但我是具有程序給出了一些困難像這樣的：如何有效計算算法的時間複雜度？

// What is time complexity of fun()? int fun(int n) { int count = 0; for (int i = n; i > 0; i /= 2) for (int j = 0; j < i; j++) count += 1; return count; }

好吧，我知道，有些人可以閉眼計算這一點，但我很想看到一個「臺階」的「一步」如何如果可能的話。

我首先要解決這將是「模擬」的輸入，並把該值在某種表的，像下面的嘗試：

for n = 100 Step i 1 100 2 50 3 25 4 12 5 6 6 3 7 1

確定在這一點上我假設這循環是O（logn），但不幸的是，正如我所說的沒有人通過「步驟」解決這個問題的「步驟」，所以最後我不知道做了什麼線索......

如果內循環我可以建立一些像下面這樣的表格：

for n = 100 Step i j 1 100 0..99 2 50 0..49 3 25 0..24 4 12 0..11 5 6 0..5 6 3 0..2 7 1 0..0

我可以看到，這兩個循環會減少，我想一個公式可以根據以上數據可以得出...

有人能澄清這個問題？（答案是O（n））

來源

2017-04-06 marcoshass

模擬它可以給你的直覺，而是得到一個明確的答案的唯一方法是分析得出的。 –

是的，我明白...但我怎麼能一步一步知道這個算法是O（n）？ – marcoshass

您已經計算了操作次數。它是n + n/2 + n/4 + ... + 1.n + n/2 + n/4 + ... + 1' <= n * SUM（1/2^k） = [0，INF）'<='N * 2'∈'爲O（n）' – DAle

另一種簡單的方法來大概看一下，它是：

你外環初始化I（可以考慮一步/迭代器）的n和每次迭代後除以2我。因此，它執行i/2語句log2（n）次。因此，想一想，您的外部循環運行log2（n）乘以。每當你用一個基數連續劃分一個數字直到它達到0時，你就可以有效地完成這個劃分日誌的次數。因此，外部循環爲O（log-base-2 n）

您的內部循環迭代迭代器j（現在是迭代器或步驟），從0到i 每次外循環迭代。我取n的最大值，因此你的內部循環的最長運行時間將從0到n。因此，它是O（n）。

現在，你的程序運行是這樣的：

Run 1: i = n, j = 0->n 
Run 2: i = n/2, j = 0->n/2 
Run 3: i = n/4, j = 0->n/4 
. 
. 
. 
Run x: i = n/(2^(x-1)), j = 0->[n/(2^(x-1))]

現在，捉迷藏時間總是「乘」爲嵌套循環，所以爲O（log-2爲底的N）*爲O（n）給出了O（ N）爲您的整個代碼

來源

2017-04-07 04:19:24

讓我們把這個分析分成幾個步驟。

首先，以inner for循環開始。這很簡單，看到這完全需要i步驟。

接下來，考慮在算法的過程中哪個不同的值i將假定。首先，考慮其中n是2的某種冪的情況。在這種情況下，i開始於n，然後n/2，然後n/4等，直到它達到1，最後是0並終止。由於內循環每次需要i步，因此在這種情況下fun(n)的總步數恰好是n + n/2 + n/4 + ... + 1 = 2n - 1。

最後，說服自己這個概括爲2的非權力。給定輸入n，找到大於n的最小功率2，並將其稱爲m。顯然，n < m < 2n，所以fun(n)需要少於2m - 1步驟，這是小於4n - 1。因此fun(n)是O(n)。

來源

2017-04-06 21:02:49 andrew

如何有效計算算法的時間複雜度？

回答

相關問題