如何找到我的算法的最佳情况和最坏情况的公式？

Question

我被分配了一项任务。编写一种算法，使得 2 个数据列表的输入至少有一个共同点。

所以，这是我的算法：（我用php编写代码）

$arrayA = array('5', '6', '1', '2', '7');
$arrayB = array('9', '2', '1', '8', '3');
$arrayC = array();

foreach($arrayA as $val){
    if(in_array($val, $arrayB)){
        array_push($arrayC, $val);
    }
}

这是我自己的算法，不确定是否好。那么，根据我的算法，如何找到最好情况和最坏情况（大O）的公式？

注意：如果我的算法错误，请告诉我。我的目标是“输入 2 个数据列表，至少有一个共同点。”

Answer 1

让您开始：

1. 你有明确的循环吗？如果是这样，他们会运行多少次（最大、最小、平均）？
2. 你有任何隐式循环吗？如果是这样，他们会运行多少次（最大、最小、平均）？
3. 这些循环中有嵌套的吗？如果是这样，他们是否相互依赖？他们以什么方式依赖

Answer 2

最坏的情况可以通过假设两个列表有一个共同的元素并且它是每个列表上的最后一个元素来找到：这将导致通过检查第二个列表的所有元素来遍历第一个列表（您正在使用

in_array

但假设你用手做，这是同样的事情

O(m)

：复杂性）。

因此，您将遍历第二个列表

n

次，复杂度将是

O(n*m)

，其中

n

是第一个列表的长度，

m

是第二个列表的长度..

要找到平均复杂度，您应该考虑一个相对于您正在计算的内容来说是平均的解决方案。这很简单，我将其作为练习。

Answer 3

在处理此类算法问题时，您必须从“算法”的角度考虑列表。也就是说，支持少量 O(1) 操作的数据类型。通常如下所示：

• 检查列表是否为空
• 在列表末尾添加一个项目
• 获取列表的第一个元素
• 从列表中删除第一个元素

这个想法是仅使用上述运算符来表达所要求的内容，然后您所要做的就是将循环执行的次数乘以循环内部内容的复杂性。

在使用进化的编程语言编写代码而不是编写算法时要非常小心，因为它隐藏了复杂性（@FrusteratedWithFormsDesign 已经暗示了这一点）。