为什么c ++算法包含最多2*(count1 + count2)-1个比较

在阅读cplusplus.com文章时,我注意到它说了以下内容:

在两个范围内最多为两倍距离的线性:执行2*(count1+count2)-1比较(其中countX是firstX和lastX之间的距离).

但是,cppreference.com指出:

最多2·(N1 + N2-1)比较,其中N1 = std :: distance(first1,last1)和N2 = std :: distance(first2,last2).

根据定义,N1 == Count1和N2 == Count2,哪个站点是正确的,并且任何人都可以解释如何计算这个最大数量或比较,即:

定义最大复杂性的最坏情况是什么？

任何人都可以解释该场景中的步骤并显示上述哪一项(cplusplus或cppreference)具有正确的比较次数？

Ieuan Stanle.. 5

警告:在阅读该帖子的每个人都意识到他们不知道他们在谈论什么(包括我)之前,已经添加了这个答案的声誉.如果在将来的某个时候有一个接受的答案,并不反对该算法的所有文档,请多加注意!

2*(无论如何)位很容易解释,我在下面这样做了.(无论如何)这一点让我感到非常困惑,据我所知,应该是这样

2*(count1)

并且与第二范围的长度完全无关.要么我错过了某些东西(最有可能),要么文档错了(不会那么好......).

如果您需要我的推理,请参阅下文.如果我错了并且有人得到了正确的答案,请告诉我,以便我可以删除这篇文章!

为什么它是2*(count1等)

如果你问为什么它是2次(count1 + count2)-1,那么关键是在这一行:

使用operator <作为第一个版本比较元素,comp作为第二个版本.如果(!(a

每次比较两个元素时,它会进行两次比较:我不等于它,它不等于我.

它所要做的这些"比较对" 的最大数量是非常难以确定的.事实上,我无法弄明白.据我所知,它应该与第二范围的长度无关......

为什么不是(count1 + count2 -1)或(count1 + count2)-1

我已经看了几天,并根据cppreference中的代码示例做了一些测试,老实说我不知道​​这是怎么回事.

算法意味着OP挖出的源代码表示range2必须是range1的子集,并且两者都是有序的,所以没有必要检查一个元素两次.这意味着算法必须最多检查range1的所有元素,另外还要检查range2的元素是否大于range1中的任何元素.不仅如此,但是在range2中有2或20个元素的位置并不重要,它仍然可以进行完全相同的比较.

有两种可能的比较定义,显然会给出不同的答案:

比较==算法中的所有比较操作

在这种情况下,会发生以下比较:

我到达了最后一个range2元素

我到达了最后一个range1元素

是range2 elem

是range2 elem> range1 elem

在简单情况下N1 == N2 == 1,这可以产生至少6个比较(1,2,3,4,1,2:其中range1 = {1},range2 = {10},例如),远远超过任何一种算法允许.所以情况并非如此.

比较==检查elem1和elem2是否相等

在这种情况下,range1的每个元素都有两个比较,直到找到range2的所有元素,或者它到达range1的末尾,在它停止时(一旦发现它已经到达range1的末尾).

因此,据我所知,复杂性与N2的长度无关,应该是复杂性

2*(N1)

请注意,对于"比较"的定义,2*(N1 + N2 - 1)仅对N2 == 1持有,而2*(N1 + N2)-1从不成立,因为比较次数仅为奇数在非最大复杂度的情况下(range2的数字不在range1且不大于max(range1)).

任何其他比较定义都是有选择性的.我能想到的唯一另一件事是编译器优化了某些步骤,比如当元素没有递增时不检查它是否再次到达range2的末尾(这也会使算法依赖于N2),但是我无法看到其他任何可以优化的东西,以便将数字降低到完全匹配所述复杂性的东西.

......其他人得到了更好的答案吗？我现在和OP一样好奇.

警告:在阅读该帖子的每个人都意识到他们不知道他们在谈论什么(包括我)之前,已经添加了这个答案的声誉.如果在将来的某个时候有一个接受的答案,并不反对该算法的所有文档,请多加注意!

2*(无论如何)位很容易解释,我在下面这样做了.(无论如何)这一点让我感到非常困惑,据我所知,应该是这样

2*(count1)

并且与第二范围的长度完全无关.要么我错过了某些东西(最有可能),要么文档错了(不会那么好......).

如果您需要我的推理,请参阅下文.如果我错了并且有人得到了正确的答案,请告诉我,以便我可以删除这篇文章!

为什么它是2*(count1等)

如果你问为什么它是2次(count1 + count2)-1,那么关键是在这一行:

使用operator <作为第一个版本比较元素,comp作为第二个版本.如果(!(a

每次比较两个元素时,它会进行两次比较:我不等于它,它不等于我.

它所要做的这些"比较对" 的最大数量是非常难以确定的.事实上,我无法弄明白.据我所知,它应该与第二范围的长度无关......

为什么不是(count1 + count2 -1)或(count1 + count2)-1

我已经看了几天,并根据cppreference中的代码示例做了一些测试,老实说我不知道​​这是怎么回事.

算法意味着OP挖出的源代码表示range2必须是range1的子集,并且两者都是有序的,所以没有必要检查一个元素两次.这意味着算法必须最多检查range1的所有元素,另外还要检查range2的元素是否大于range1中的任何元素.不仅如此,但是在range2中有2或20个元素的位置并不重要,它仍然可以进行完全相同的比较.

有两种可能的比较定义,显然会给出不同的答案:

比较==算法中的所有比较操作

在这种情况下,会发生以下比较:

我到达了最后一个range2元素

我到达了最后一个range1元素

是range2 elem

是range2 elem> range1 elem

在简单情况下N1 == N2 == 1,这可以产生至少6个比较(1,2,3,4,1,2:其中range1 = {1},range2 = {10},例如),远远超过任何一种算法允许.所以情况并非如此.

比较==检查elem1和elem2是否相等

在这种情况下,range1的每个元素都有两个比较,直到找到range2的所有元素,或者它到达range1的末尾,在它停止时(一旦发现它已经到达range1的末尾).

因此,据我所知,复杂性与N2的长度无关,应该是复杂性

2*(N1)

请注意,对于"比较"的定义,2*(N1 + N2 - 1)仅对N2 == 1持有,而2*(N1 + N2)-1从不成立,因为比较次数仅为奇数在非最大复杂度的情况下(range2的数字不在range1且不大于max(range1)).

任何其他比较定义都是有选择性的.我能想到的唯一另一件事是编译器优化了某些步骤,比如当元素没有递增时不检查它是否再次到达range2的末尾(这也会使算法依赖于N2),但是我无法看到其他任何可以优化的东西,以便将数字降低到完全匹配所述复杂性的东西.

......其他人得到了更好的答案吗？我现在和OP一样好奇.