爲什麼單詞O（n）的句子的逆時間複雜度？

我碰到這個文章來Reverse words in a given string 爲什麼單詞O（n）的句子的逆時間複雜度？

的代碼是

void reverseWords(char *s) 
{ 
    char *word_begin = NULL; 
    char *temp = s; /* temp is for word boundry */ 

    /*STEP 1 of the above algorithm */ 
    while(*temp) 
    { 
     /*This condition is to make sure that the string start with 
      valid character (not space) only*/ 
     if ((word_begin == NULL) && (*temp != ' ')) 
     { 
      word_begin=temp; 
     } 
     if(word_begin && ((*(temp+1) == ' ') || (*(temp+1) == '\0'))) 
     { 
      reverse(word_begin, temp); 
      word_begin = NULL; 
     } 
     temp++; 
    } /* End of while */ 

    /*STEP 2 of the above algorithm */ 
    reverse(s, temp-1); 
}

我的時間複雜度的理解這個問題：

1）遍歷整個字符串，因此O(n)，n = length of the array

2 ）反向時間複雜度爲O(m/2)m = size of word reversing

爲什麼不是時間複雜度O(n * (m/2))這是O(nm) ?

但在鏈接中提到的時間複雜度爲O(n)。的reverse method?

來源

2017-08-23 Newbie

當你說逆時間複雜度是'O（n/2）'時，'n'是什麼？你正在翻轉的單詞的大小？對於整個字符串，與'O（n）'中的'n'不同嗎？那麼爲什麼爲兩個不同的值使用相同的變量？ –

我根據你的問題編輯了這個問題。 – Newbie

那麼'n'和'm'之間的關係是什麼？他們顯然不是獨立的。例如，200個字母的句子不能有300個字母的單詞，對吧？另外，每次迭代都不會調用「reverse」，僅在某些情況下。所以你不能只乘以它們。（不斷修正你的錯誤，你最終會同意給出的答案。） –

爲什麼我們忽略了時間複雜度爲什麼不是時間複雜度O(n * (m/2))這是O(nm)？

因爲你不按每個字符扭轉的話，你只能做一次每m字符。因此，雖然掃描單詞，然後反向它給你O(m)（兩次m，這仍然是O(m)），整個過程需要n/m * O(m) = O(n)，因爲只有n/m單詞。

（更確切地說，對於字長m1，m2，......，每一個字取O(m_i)步驟，以及s空白的總量，該算法需要O(m1) + O(m2) + ... + O(s) = O(m1 + m2 + ... + s) = O(n)，字長和總結，以n空白的總量。）

來源

2017-08-23 02:35:29 bipll

爲什麼單詞O（n）的句子的逆時間複雜度？

回答

相關問題