簡單的算法分析

我想要一個算法至少O（n ^（3/2））的複雜性。算法如下：簡單的算法分析

function(string s, int n) 
{ 
    bool result = false; 
    int position = 0; 
    for(int i = 0; i < n/2; i++) 
    { 
     position = 0; 
     for(int j = i+1; j < n; j++) 
     { 
      if(s[j] != s[position]) break;   
      if(j == n) result = true; 
      if(position == i) position = 0; 
      else position++;   
     } 
     if(result) break;  
    } 
    return result; 
}

第一個for循環會迭代n/2次，這是O（n）複雜度。我需要讓內部for-loop最多爲O（sqrt（n）），從而使整個算法具有O（n ^（3/2））的複雜性。我很難弄清楚嵌套for循環是否是我需要的正確複雜性。

注意：
n是字符串的大小。該功能基本上檢查是否在字符串s中出現重複模式。 s中唯一的字符是"0"和"1"。例如，如果字符串爲"001001"，則該模式爲"001"，並且發生兩次。字符串也是偶數。話雖如此，語法和功能上與這個問題無關。所有的基本動作都被認爲是O（1）（恆定）時間，這幾乎是整個代碼。

注2：
我正在做這個作業。但作業問題只是爲了讓算法運行，我已經完成了。降低複雜性只是額外的練習。

任何幫助或指導，將不勝感激！

來源

2012-05-17 Tesla

該算法的作用是什麼？ –

我在代碼下的「註釋：」中解釋了這一點。它確定字符串s是否包含重複模式。例如，「001001」由「001」組成兩次。「000000」組成「0」6次。「010100」將是一個不是由模式組成的例子。 – Tesla

這是一個O（N）工作。你需要稍微修改一下字符串搜索算法。 –

這很簡單，只需檢查長度是否將總長度分開（它必須，如果L沒有劃分總長度，則字符串不能是長度爲L的重複模式），並且不運行內部循環，如果它不...限制數的上限是2sqrt（n），所以這保證了O（Nsqrt（N））。

如果您想知道爲什麼，數字的最大數量可能是每個數字達到sqrt（n），然後對於每個數字x，N/x。所以在2sqrt（N）以下。

當然，實際上，除了12個實際上包含所有這些因子的數字外，實際上數字的因子更少：1,2,3（每個數字至sqrt），12/1,12/2,12/3 （逆）。

有2個內部循環，但一個運行L次，另一個N/L次，所以內部循環是O（N）。

static bool f(string s) 
    { 
     int n = s.Length; 
     for (int l = n/2; l >= 1; l--) 
     { 
      if (n % l != 0) continue; 
      bool d = true; 
      for (int o = 0; o < l; o++) 
      { 
       char f = s[o]; 
       for (int p = l; p < n; p += l) 
        if (s[p + o] != f) d = false; 
      } 
      if (d == true) return true; 
     } 
     return false; 
    }

關鍵行是：

if (n % l != 0) continue;

否則這將是O（N^2）。

雖然外圈看起來似乎是乍一看是N/2，但在數學上保證是< 2sqrt（N）。你可以通過在幾百萬字符的字符串上運行來看到它 - 它會很快運行。

來源

2012-05-17 12:31:25 svinja

哦，這很有道理。我迷惑了自己內心循環的複雜程度。非常感謝，這解決了一些事情！ – Tesla

我認爲你的內循環不能被放到O（sqrt（n）），因爲你必須比較從字符串開始到特定索引i的值，這些字符的值由外部循環控制。

來源

2012-05-17 02:28:35

它說整體算法可以完成O（n^3/2）的複雜性。我認爲外部循環必須是O（n），然後是內部O（sqrt（n）），這就是我設計它的方式。它是否應該翻轉？ – Tesla

是的，它應該翻轉。 –

簡單的算法分析

回答

相關問題