時間和空間複雜的語言複雜性

-1

int foo(char *str) 
{ 
    char *p = str; 
    while (p && *p!='\0' && 
     ((*p >= 'a' && *p <= 'z') 
      || (*p >= 'A' && *p <= 'Z') || *p == '@')) { 
     p++; 
    } 
    return p-str; 
}

以上覆雜的while語句的時間和空間複雜程度如何。它依賴於任何報表中，而EN-接近 while (p && *p!='\0' && ((*p >= 'a' && *p <= 'z') || (*p >= 'A' && *p <= 'Z') || *p == '@'))時間和空間複雜的語言複雜性

或者只在while體如上

while(){ 
//body statements 
    p++; 
}

。這也取決於短路&&或||。

來源

2012-09-03 Yogesh R.L

聽起來像功課 –

聽起來像'O（n）' – nullpotent

如果我是你，我會更少擔心性能和更多可讀性:-)可能的可移植性 - 不是_everyone_使用ASCII。 – paxdiablo

當您談論複雜性時，您將根據輸入大小討論其增長的程度。在這種情況下，它基於作爲str傳入的字符串的大小。在while條件下檢查的東西數量不會改變。它固定在算法中，稱爲「常數因子」，所以我們不計算它。由於在最壞的情況下，測試在字符串的每個字符上運行一次，它是O(n)，其中n是字符串的長度。

來源

2012-09-03 04:00:38

我不知道你的運行時間或空間複雜度，但實際的條件複雜度可以被大大簡化，使其更具可讀性。首先，您不必在每個循環中檢查指針p，請先檢查str是否爲單獨檢查中的非空指針。其次，你應該使用isalpha來檢查字母。

因此，代碼看起來是這樣的，而不是：

int foo(char *str) 
{ 
    if (str == NULL) 
     return 0; 

    char *p = str; 
    while (*p != '\0' && (isalpha(*p) || *p == '@')) 
     p++; 

    return p - str; 
}

使用isalpha幫助您在評論你的問題指出這些問題，同時也有效，即使您的語言環境被改變。

來源

2012-09-03 06:44:35

時間和空間複雜的語言複雜性

回答

相關問題