這些循環1和2的時間複雜度是多少

我正在閱讀一篇關於在非常流行的網站上分析循環時間複雜性的文章（下面給出的鏈接），並根據該文章介紹了下面循環的時間複雜性1st和第二個分別是O（1）和O（n）。但我認爲這兩個循環的時間複雜度是相同的O（n）的這些循環1和2的時間複雜度是多少

for (int i = 1; i <= c; i++) { 
    // some O(1) expressions 
}

我的理由是：'C * N = O（n）的

通過回答以下問題，會後，我的理由是因爲沒有變化的輸入n錯誤。循環運行是固定的--c次。因此不管輸入值n如何，循環將運行恆定時間。所以O（1）複雜

for (int i = 1; i <= n; i += c) { 
    // some O(1) expressions 
}

我的理由：c*n=O(n)

我失去的東西，我將不勝感激，如果有人能幫助解釋

這是文章的鏈接？ http://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/

來源

2015-09-12 Deen John

循環或遞歸運行的次數也是認爲是O（1）。

這裏：C是一個常數值。所以基本上，你不考慮價值的n

// Here c is a constant 
    for (int i = 1; i <= c; i++) { 
     // some O(1) expressions 
    }

此外，在第二循環中執行操作的常數：

for (int i = 1; i <= n; i += c) { 
    // some O(1) expressions 
}

你的理由c*n = O(n)是不正確。這裏增加C。對於n元素，環存在n/c這是漸近O(n/c) ~ O(n)

來源

2015-09-12 07:01:24

這整個循環就像一個常數，因爲它不依賴於變化的輸入值 - 循環是固定的？ right –

@Naruto_Uzumaki嗯是的循環是固定的。你對 –

非常感謝Sakib兩種情況。我現在明白清楚 –

1）圖片中沒有n，我不知道爲什麼你認爲它O(n)。 loop是從1 to c，所以它的O(c)，和c是一個常數，複雜性是O(1)。

2）循環從1開始，直到n，在每一步遞增c。顯然複雜度爲O(n/c)，漸近爲O(n)。

來源

2015-09-12 06:50:37 Haris

感謝哈里斯，我更正了O（c）部分 –

@Harish：所以兩個循環都具有O（n）複雜性？正確：因爲在這兩種情況下，常量內部循環打印的次數（ - 將此視爲循環中的常量表達式）取決於輸入的值：n –

@Naruto_Uzumaki是的。 – Haris

對（INT I = 1;我< = C;我++）{//一些O（1）的表達式}

c這裏爲常數。因此，基本上，您正在執行恆定數量的操作，而不管n的值如何。這就是爲什麼它被認爲是不變的複雜性，O(1)。

對（INT I = 1;我< = N; I + = C）{//一些O（1）的表達式}

您正與一個輸入值n，這是循環基本上隨程序或算法的給定輸入而變化。現在c又是一個常量，對於n的所有不同值，它將保持不變。複雜度被認爲是O(n)。

的for（int i = 1;我< = N;我++）{//一些O（1）的表達式}

這是相同c唯一同上，只是該值是1。

所有的複雜性都在漸近符號格式中表示。常數因子被刪除，因爲它們將與n的值無關。

來源

2015-09-12 06:55:32 YoungHobbit

他改變了問題，再次經歷。 – Haris

好吧，讓我們把一個簡單的打印語句-SOP（「hello World」） - 在這兩個循環裏面，現在不是這個打印多少次依賴於輸入的值：n？總的來說，不應該是時間複雜度恆定的打印單次與輸入相乘的時間是多少？ –

請現在檢查答案。 – YoungHobbit

O（1）：的這個循環的複雜度是O（1），因爲它運行時刻c的恆定量。

// Here c is a constant 
    for (int i = 1; i <= c; i++) { 
     // some O(1) expressions 
    }

爲O（n）：環路的複雜性爲O（n），如果它被遞增或通過恆定量遞減。例如，這些循環具有O（n）時間複雜度。

// Here c is a positive integer constant 
    for (int i = 1; i <= n; i += c) { 
     // some O(1) expressions 
    } 

    for (int i = n; i > 0; i -= c) { 
     // some O(1) expressions 
    }

來源

2015-09-12 19:17:41 Codessci

這些循環1和2的時間複雜度是多少

回答

相關問題