比较两个字符串的复杂性

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),因为你只穿过针阵列.