時間這個算法不斷循環

-3

for(int i = 0; i < 1337; i++){ 
    printf("\n"); 
    }

是O（1），因爲我們有不論n

但怎麼樣：

char * s = "abcdef"; 
for(int i = 0; i < 1337; i++){ 
     strlen(s); 
     }

是這樣的O（N） now？請任何一位解釋

來源

2017-04-13 gar

第二個例子中是否有N個？ –

以及在上述兩種情況下，TC應該有什麼不同？ –

現在是O（| s |）的O（1337 * | s |），如果你的意思是s是可變的。但是你的問題到底是什麼，我還是不明白... – shole

如果你有一個不變的輸入，算法的複雜度將總是爲O（1），因爲你將執行相同數量的操作。

但是，如果輸入s算法，複雜度將變爲O(len(s))。請注意，O(N)在這個例子中沒有意義，因爲您沒有沒有定義什麼是N。

來源

2017-04-13 07:58:34

-1

它仍然是O（1），因爲你仍然在循環次數不變。它不會改變，如果你改變任何給定的變量的值。

來源

2017-04-13 08:00:03 Sham3r

您需要定義什麼N是。你的第一個例子是O（1），不管你如何看待它。你的第二個例子是O（N）的長度爲s，因爲strlen是O（N）。

來源

2017-04-13 08:00:39

誰想出了定義所有東西的想法？在大O符號中，字面上任何東西都可以作爲描述符。如果我寫'O（M^N）'，那麼很明顯複雜度被一些表示爲M和N的可變部分所約束，複雜度爲M^N，只有當我想詳細討論期望的值範圍有助於瞭解「M」和「N」的起源。抽象複雜性語句不需要這麼做 – grek40

@ grek40 - 不確定你的意思 - 如果你不指定什麼輸入/變量/等等。 N涉及到那麼O（N）是相當無意義的。 –

@OliverCharlesworth在某種程度上需要有一個定義。然而，我認爲在big-O的情況下，任何顯示的「M，N，...」（除非另有定義）都可以被解釋爲表示一些線性縮放輸入，這有助於表示方式的複雜性。並不是每個人都對代表性的詳細映射感興趣。現在，當我有一個線性複雜性約束時，即使不知道詳細的「N」，我也可以使用任何有限次數的「O（N）」函數。 – grek40

時間這個算法不斷循環

回答

相關問題