比较两个字符串的复杂性

Question

$haystack = array('T', 'h', 'i', 's', 'i', 's', 's', 'r', 'i', 'k', 'a', 'n', 't', 'h'); 
$needle = array('s', 'r', 'i', 'k', 'a', 'n', 't', 'h'); 
$array = array(); 
$k = -1; 

$m = count($needle); 
$n = count($haystack); 
//****************1st type******************** 
for ($i = 0; $i < $m; $i++) { 
    for ($j = 0; $j < $n; $j++) { 
     if ($needle[$i] == $haystack[$j]) { 
      $array[++$k] = $needle[$i]; 
      //echo $needle[$i]."<br/>"; 
      break; 
     } 
    } 
} 
//********************2nd type************************** 
$found_array = array(); 
$j = 0; 
for ($i = 0; $i < $n; $i++) { 
    if ($needle[$j] == $haystack[$i]) { 
     $found_array[] = $needle[$j]; 
     $j++; 
    } 
} 

echo '<pre>'; 
print_r($array); 
echo '</pre>'; 

echo '<pre>'; 
print_r($found_array); 
echo '</pre>'; 

正如您所看到的，我正在比较2个字符串...使用2种不同类型。 他们每个人的复杂性是什么？ 我的答案是O（NM）都是..我正确吗???

Answer 1

最上面的一个是O（NM），因为你有两个嵌套for循环。

底部是O（N），因为您只能穿过针阵列。