c++ - 两种常见比较算法的比较及其Big O帮助

Question

今天我的教授给了我们 2 个带回家的问题作为即将到来的 C 数组单元的练习，我想知道这 2 个问题到底类似于什么排序算法以及它们的大 O 是什么。 现在，我来这里不是为了期待答案，我已经已经解决了这些问题，但我对自己的答案并不自信，所以我会发布他们把每个问题都弄清楚了，如果我错了，请纠正我并解释我的思维错误。

问题 1:

如果我们决定一次遍历一个数组的(框)元素(文件夹)。从第一个元素开始并将其与下一个元素进行比较。然后，如果它们相同，则比较结束，但如果两者不相等，则继续比较下两个元素 [2] 和 [3]。重复此过程并将在比较最后两个元素后停止并注意数组已按姓氏排序并且我们正在寻找相同的名字!示例:[ Harper Steven、Hawking John、Ingleton Steven]

我相信的答案:

我相信它是 O(n)，因为它只是遍历数组的元素，比较数组 [0] 和数组 [1]，然后比较数组 [2] 和数组 [3] 等等。这个过程是线性的，并一直持续到比较完最后两个。绝对不是 logn，因为我们不是乘以或潜水 2。

最后一个问题:假设我们有一盒文件夹，每个文件夹包含一个人的信息。如果我们想找同名的人，我们可以先在盒子里的第一个文件夹上贴上标签，然后按顺序遍历它后面的文件夹，直到找到同名的人。如果我们找到同名的文件夹，我们会将该文件夹移动到带有标签的文件夹旁边。一旦我们发现两个人同名的情况，我们就会停下来 sleep ，因为我们很懒惰。但是，如果第一次搜索失败，我们只需删除贴纸并将其放在下一个文件夹中，然后像之前那样继续。在我们没有两个同名的人的情况下，我们重复这个过程，直到贴纸在最后一个文件夹上。

此数组未排序，并将第一个文件夹与 sticker folder[0] 与下一个 i folder[i] 元素进行比较。

我的回答:

我觉得这不可能是 O(n)，但可能是 O(n^2)，感觉我们有一个数组，然后我们不断重复这个过程，其中 n 与输入的平方成正比(文件夹)。我在这里可能是错的 >.>

Answer 1

你在这两个问题上都是对的……但它会有助于更严格地解释事情。我不知道你们类(class)的标准是什么；您可能不需要实际证明，但展示比“我们不乘以或除以二”更详细的推理永远不会有坏处。所以……

---

在第一个问题中，这里显然没有发生任何事情，只有比较，所以这就是我们必须计算的。

最坏的情况显然是你必须遍历整个数组。

所以，在那种情况下，你必须比较a[0] == a[1]，然后是a[1] == a[2]， …, a[N-1] == a[N]。对于每个 N-1 元素，都有 1 次比较。那是 N-1 个步骤，显然是 O(N)。

事实证明，数组已排序这一事实在这里是无关紧要的。 (当然，因为它们不是按您的搜索键排序的——也就是说，它们是按姓氏排序的，但您是按名字进行比较的——这已经很明显了。)

---

在第二个问题中，这里发生了两件事:比较，然后移动。

对于比较，最坏的情况是您必须执行所有 N 搜索，因为没有匹配项。正如您所说，我们从 a[0] 开始，而不是 a[1]，...，a[N]；然后 a[1] 与 a[2]，...，a[N] 等。所以，N-1 比较，然后是 N-2，依此类推直到 0。所以总的比较次数为sum(0…N-1)，即N*(N-1)/2，即N^2/2 - N/2，即 O(N^2)。

对于移动，最坏的情况是您找到 a[0] 和 a[N] 之间的匹配。在这种情况下，您必须将 a[N] 与 a[N-1] 交换，然后将 a[N-1] 与 a[N-2]，依此类推，直到您将 a[2] 替换为 a[1]。所以，这是 N-1 交换，也就是 O(N)，您可以忽略它，因为您已经有了 O(N^2) 术语。

---

作为旁注，根据您的描述，我不确定您是在谈论来自 a[0…N] 的数组，还是长度为 N 的数组，所以 a[0…N-1]，所以上面两个都可能存在差一错误。但向您自己证明这并没有什么不同应该很容易。