時間複雜度如何不同？

Question

如果該值先存儲然後再使用，是否節省時間？例如：
;

while(i<strlen(s)) 
//code 

和

int n = strlen(s); 
while(i<n) 
//code 

是用於第二方法下的時間複雜度作爲函數的返回值首先被存儲，然後使用，從而避免了在每次進入循環時間調用函數？

Answer 1

在第一示例中，假定i適當地初始化（至0可能）和在循環體被遞增，你會計算圍繞每個時間字符串s中的字符數循環，所以如果字符串中有N個字符，則會執行N 比較（因爲strlen()將字符串中的每個字符與'\0'進行比較，並且您將執行顯式循環N次，並且循環內部爲strlen()每次通話N次），使碼爲O（N ）。

在第二個例子中，再次假設i在循環體中被初始化並增加，您將計算一次字符數，因此您將進行N次比較，從而生成代碼O（N）。

優化程序是否可以安全地優化strlen()不在環路控制之外的呼叫取決於循環體中的內容。如果編譯器可以看到所有內容，或者可以確定被調用的代碼不能合法地修改字符串s，那麼它可能會將呼叫移到strlen()之外的循環控制，從而有效地提供第二個循環的O（N）性能。 OTOH，如果循環的主體調用函數並將非const指針傳遞給函數s，則編譯器可能無法假定該字符串未修改，並且可能必須在每次迭代時調用strlen()。

Answer 2

一個聰明的編譯器會爲你做第二個。所以不要擔心這一點，不要成爲過早優化的受害者！

---

你想要第二個，因爲長度有一個固定的值，你將避免每個循環的函數調用。

---

但是編譯器是否足夠聰明呢？只有你也告訴他！看下面的例子：

首先，我編譯沒有優化標誌：

C02QT2UBFVH6-lm:~ gsamaras$ gcc -Wall nostore.c 
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out 
That took 27.701602000 seconds wall clock time. 
C02QT2UBFVH6-lm:~ gsamaras$ gcc -Wall store.c 
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out 
That took 12.100676000 seconds wall clock time. 

但是如果我們使用優化的標誌，會發生什麼？

C02QT2UBFVH6-lm:~ gsamaras$ gcc -O3 -Wall nostore.c 
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out 
That took 0.004949000 seconds wall clock time. 
C02QT2UBFVH6-lm:~ gsamaras$ gcc -O3 -Wall store.c 
C02QT2UBFVH6-lm:~ gsamaras$ ./a.out 
That took 0.005283000 seconds wall clock time. 

編譯器做得比我好！如今有些人錯誤地認爲編譯器並不那麼愚蠢。

對於時間我使用了我的Time measurements Nomimal Animal的方法。

這裏是我執行的鱈魚：

char* str = "What's faster? What's a premature optimization? Am I a vi$ 
int i = INT_MAX; 

// int n = strlen(str); 
// while(n); 
while(strlen(str)) { 
    // do some random work so that you don't get 0 timing 
    int a = 3; 
    double pi = 3.14; 
    a /= pi; 
    a = a % (i + 1); 
    // break when 'i' is 0 
    if(!i) 
     break; 
    --i; 
} 

---

但優化的標誌，在基準測試重要嗎？ YES，檢查這樣的問題：Poor performance of stl list on vs2015 while deleting nodes which contain iterator to self's position in list