complexité de comparer deux chaînes

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>'; 

Comme vous pouvez le voir, je compare 2 chaînes ... en utilisant 2 types différents. quelle est la complexité de chacun d'entre eux? Ma réponse est O (NM) pour les deux..Am je correcte ???

Answer 1

le premier est O (NM) parce que vous avez les deux boucles imbriquées.

La ligne inférieure est O (N) car vous ne faites que traverser le réseau d'aiguilles.