時間複雜度

這個問題是修訂的目的從過去的考卷我只是想知道如果我在正確的軌道時間複雜度

1. int i=1; 
2. while (i <= n) { 
3. for (int j=1; j<10; j++) 
4.  sum++; 
5. i++; 
6. } 
7. for(int j = 1; j <= n; j++) 
8. for(int k = 1; k <= n; k=k*2) 
9.  sum++;

1）的聲明4執行多少次？
A.爲O（n）
B.爲O（n^2）
C. O（log n）的
D.爲O（n log n）的
E.沒有的上述

在這裏，我選擇A

2.）語句9執行多少次？
A.爲O（n）
B.爲O（n^2）
C. O（log n）的
D.爲O（n log n）的
E.以上皆非

因爲線的8（k = k * 2）我選擇C

3.）整個代碼片段的運行時間是多少？
A. 爲O（n）
B.爲O（n^2）
C. O（log n）的
D.爲O（n log n）的

由於爲O（n）+ O（LOGN ）= O（n）所以我選擇了A

來源

2011-05-23 Annita Zirki

@尼爾：你爲什麼這麼認爲？（當然，這不是完整的考卷。） – ShreevatsaR 2011-05-23 07:22:47

@ShreevatsaR：可能是因爲大O既不是數量（「多少次......」），也不是持續時間（「什麼是運行時間......「）。更好的是更準確的「什麼是...的時間複雜度？」。 – paxdiablo 2011-05-23 07:24:48

@paxdiablo：說「語句4被執行的次數是O（n）」是完全準確的。即，量/函數10n是O（n）。（一個完全不同的問題是，紙可能要求Theta，或要求最小的正確的O（。），但這是可以原諒的，取決於課程的級別。） – ShreevatsaR 2011-05-23 07:27:00

你的回答1是正確的，它在一個僅由n控制的循環內。

答案2不正確。它將爲O(log n)如果第7行不存在，但由於第7行強制行8和9依賴於n多次運行，答案是O(n log n)。

答案3是正確的推理但患有這個事實答案2是錯誤的。 O(n) + O(n log n)簡化爲O(n log n)。

所以答案是A,D和D。

來源

2011-05-23 07:09:45 paxdiablo

@Annita：如果這個答案對你有幫助，你可以通過點擊旁邊的勾號來「接受」它。 – ShreevatsaR 2011-05-23 07:34:59

該行下的評論是錯誤的。大O不說時間;它指定了漸近複雜度，通常用一些特定的操作來表示。從這個意義上說，它更接近於「一段代碼運行多少次」，而不是涉及到運行時的任何事情（這也取決於諸如局部性之類的事情---大-O總是假定任何給定操作是恆定時間的，其中因爲內存訪問因緩存而異）。 – 2011-05-23 09:16:01

@詹姆斯，「時間複雜度」的括號表示清楚表明我們在這裏談論時間。 – paxdiablo 2011-05-23 15:58:02

我不知道如何制定問題，但如果措辭就像你說的那樣，考官並不知道大O的正確定義（至少在他期待「正確」的答案時） - 作爲「大O函數包括更小的「。因此，在f（n）= 10 n中線性的函數n也是在O（n），O（n^2），O（n log n）中執行的。如果有人問，對於「最小」可能的話，你的答案會是

聲明4執行10 N倍，所以A
聲明9執行的n * log n次，所以d
這裏它執行兩者的總和，n + n * log n所以（這裏你失去了一個* n），所以D就是正確的。

所以，如果可以有多種答案，它只是要求它有多少執行，正確的答案是

A，B，d
B，d
乙，D

來源

2011-05-23 07:18:45 flolo

問題2中的* n * log * n *答案是D，而不是C. – 2011-05-23 07:23:20

是的，已經修復它，誤解了問題中的字母。 – flolo 2011-05-23 07:25:05

我遇到的每個導師和考官總是含蓄地指*最小的正確*大O當他們談論/詢問關於某事物的大O時，除非他們需要使用屬性，如果函數是O（某物）而不是它也是O（更大的東西）。 – 2011-05-23 07:42:41

答案1：A ie。 O（n）作爲陳述4將被執行10 * n次。

答案2：D ie。 O（nlog（n））作爲語句9將執行n * log（n）次。答案3：作爲總體複雜度[O（n）+ O（nlog（n））]的D將是n * log（n）。

來源

2011-05-23 08:34:20 bayCoder

回答

相關問題