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

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)， whilein_array更可能是线性搜索，其中array_2将进行 1 次操作（作为第一个元素找到）直至array_2操作长度。

请注意，in_array这里代表唯一的变量：

• 最好的情况：in_array在第一次比较时返回 --> 的所有元素array_1都相同，并且要么array_2为空，要么等于其第一个元素。复杂性是O(N)因为我们有N元素array_1
• 最坏的情况：每次我们检查array_2--> 的每个元素时，所有元素array_1都是不同的，并且它们与 之前的元素不同array_2。如果M是输入时的长度array_2，那么复杂度沿着 的线O(N * (N+M) )，是从到元素增长时(N+M)/2搜索的平均时间，并且在符号中被丢弃的常量array_2MM+N2O

希望这可以帮助。