php - 如何确定程序(算法)的最佳情况和最坏情况？

Question

假设我有这个程序，我想比较 2 个输入列表。假设数组 A 和数组 B。如何确定函数的最佳情况和最坏情况？

这是我在 [php] 中的代码:

foreach($array_1 as $k){
    if(!in_array($k, $array_2)){
        array_push($array_2, $k);
    }
}   

for 循环的最佳情况和最坏情况是什么？请包括一些解释，谢谢:)

编辑:

因为我的目标是比较具有至少 1 个共同元素的 2 个列表。我认为我上面的代码是错误的。这是我的代码的更新

foreach($array_1 as $k){
    if(in_array($k, $array_2)){
        array_push($array_3, $k);
    }
}

我猜会是:

最好的情况:O(n)

最坏情况:O(N*M)

Answer 1

那么让我们快速分析一下:

foreach($array_1 as $k)

表示将对数组的每个元素重复其中的操作。用 N 表示数组的大小。

内部操作:

if (!in_array($k, $array_2)) {
  array_push($array_2, $k);
}

这里有2个操作:

• in_array
• array_push

array_push 可能是常量，因此 O(1)，而 in_array 更可能是 array_2 中的线性搜索 这将采用 1 个操作(作为第一个元素找到)，直到 array_2 操作的长度。

请注意，in_array 代表此处唯一的变量:

• 最佳情况:in_array 在第一次比较时返回 --> array_1 的所有元素都相同，并且 array_2 为空或它们等于它的第一个元素。复杂度为 O(N)，因为我们在 array_1
中有 N 个元素
• 最坏情况:每次我们检查 array_2 的每个元素时 --> array_1 的所有元素都是不同的，并且它们与 array_2 的先前元素不同。如果输入时M是array_2的长度，那么复杂度是O(N * (N+M) )，(N+M)/2 是在 array_2 中搜索的平均时间，因为它从 M 增长到 M+N 元素和常量 2 在 O 表示法中被丢弃

希望这对您有所帮助。