Big O（）圆形搜索算法的性能：1单向，双向 [英] Big O () Performance for a searching algorithm in a circle: 1 unidirectional, 2- Bidirectional

问题描述

如果我按顺序组织了n个元素，那么一个圆圈为x1，x2，x3，..，xn，并且圆圈环绕：xn后面跟着x1。

每个元素都可以执行搜索任何其他元素。

每个元素都可以将查询转发给它的邻居。



在这个圈子中搜索元素xm的表现如果：

1-我允许搜索仅在一个方向上。即：如果Xi正在搜索Xm，则搜索只能从Xi - > Xi + 1 - > Xi + 2 ...顺序进行，直到找到Xm。



2-我允许搜索是双向的。即：每个元素都可以以任一方式转发查询。如果Xi正在搜索Xm，则查询可以是：Xi - > Xi + 1 - > Xi + 2 ...--> Xm或Xi - > Xi-1 - > Xi -2 ...--> Xm



我的直觉是，对于第一种情况，最坏的情况是xm = xn ==> O（n）和第二个最坏的情况是如果xm在x1和xn之间的中间==>是O（n / 2）



注意：我可以确定第二种情况下搜索的方向。例如：如果我将正元素放在右侧而负元素放在另一侧，我正在从值为0的元素执行搜索。元素0知道如果我要查找的元素是正数我应该搜索在右边。等等

If I have n element organized in sequence is a circle as x1, x2, x3,..,xn and the circle wraps around: xn will be followed by x1.
Each element can perform a search for any other element.
Each element can forward the query to its adjacent neighbor.

What is the performance of searching for an element xm in this circle if:
1- I allow the search to be in one direction only. i.e.: if Xi is searching for Xm, the search can only proceed sequentially from Xi-->Xi+1-->Xi+2... until Xm is found.

2- I allow the search to be bi-directional. i.e.: each element can forward the query either way. If Xi is searching for Xm, the query could go either: Xi-->Xi+1-->Xi+2...-->Xm or Xi-->Xi-1-->Xi-2...-->Xm

My intuition is that for the first case the worst case is if xm=xn ==> O(n) and for the second one the worst case would be if xm is in the middle between x1 and xn ==> is O(n/2)

Note: I can determine which direction the search can go for the second case. For example: If I put the positive elements on right side and the negative elements on the other side and I am performing my search from an element with the value 0. Element 0 knows that if the element I am looking for is positive I should search on the right. etc.

推荐答案

我看不出差异...... O（n）意味着（在最坏的情况下）你必须访问每个节点才能得到答案。

如果从开始到结束或从两端到中间检查它都不会改变...

至于检查一个项目是一个恒定的时间并且你要检查两种方法中的所有项目（在最坏的情况下）没有区别，机器人最多有O（n）......

I can't see the difference... O(n) means that (in worst case) you have to visit every node to get the answer.
It does not changes if you check it from the beginning to the end or from both end to the middle...
As to check one item is a constant time and you ave to check all items (in worst case) in both method there is no difference and bot have a maximum of O(n)...

在所有情况下，时间复杂度仍然是O（N）。原因如下：要找到一个元素，在更糟糕的情况下，您仍然需要逐个测试所有元素。从不同方向搜索或从另一个元素开始搜索不会改变任何内容。



此外，您应该看到复杂性和性能之间的差异。 Big-O是衡量复杂性的标准，而不是绩效。例如，您可以使用N个独立的CPU核心同时搜索N个片段。它将通过N因子减去实现并行机制的一些开销来改善性能。但它不会提高复杂性。

-SA

In all your cases, the time complexity is still O(N). Here is why: to find just one element, in worse-case scenario you still have to test all elements one by one. The search in different directions or starting the search from another element changes nothing.

Also, you should see the difference between complexity and performance. Big-O is the measure of complexity, not performance. For example, you can search in N fragments at the same time using N separate CPU cores. It would improve the performance by the factor of N minus some overhead for implementation of parallel mechanism. But it would not improve complexity.

—SA

这篇关于Big O（）圆形搜索算法的性能：1单向，双向的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！