比较两个字符串的复杂性

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)，因为您只遍历针阵列。