多重二进制搜索和比较算法的复杂性

Question

Hello,

I have two questions regarding complexity:

1) What would be the Best/worst complexity of a binary search called multiple times. In other words a binary search used to compare two arrays. I believe one of them is O(mlog(n)) (no matches between arrays). However, since I can't figure out the other, I can't tell if this is the best or worst.

2) For the following segment of code: Two arrays A of size m and B of size n where m>=n, and where A and B have gone through a bubble sort each. In addition no elements in A are repeated. And no elements in B are repeated. However, A and B have may have common elements. The following pseudo-code computes the number of common elements:
count = 0
for i from 0 to m:
 if i < n:
  for j from 0 to n:
     if A[i]==B[j]:
       count + =1
       break
 else:
    break
I seem to come up with the following complexities for the sort and comparison:

bubble sort has worst O(n^2) and best O(n)

search has two bounds ( I think): situation 1: no matches O(mn), situation 2: The first n elements of array A(size m) match to all of the elements of array B(size n). -> O(n^2)

Complexity possibilities (sort and search): O(n^2+mn),O(n+mn),O(n^2+n)=O(n^2) The best seems to be sorted and no matches O(mn+n) The worst seems to be not sorted and no matches O(n^2+mn) Does this seem valid?

谢谢。

P.S。对不起，整个事情都是块格式。不提交就不让我提交。

Answer 1

如果数组已排序为什么在 O(n) <= O(n+m-c) <= O(n+m) 中可以完成两个操作时为什么要使用二进制搜索或 m:n 组合比较？

问题 2 的操作示例：

int c=0; // common elements
for (int i=0,j=0;(i<m)&&(j<n);)
 {
      if (a[i]==b[i]) { c++; i++; j++; }
 else if (a[i]< b[i]) i++;
 else                   j++;
 }

如果需要，只需在数组末尾添加一些 ifs（不确定它是否不会忽略最后一个公共元素并且懒得分析它）但是无论如何你会看到如何更快地解决此类问题
可以对比较进行同样的操作，但您没有提供有关其目的的任何详细信息...

现在回到你的问题：

如果你解析数组的每个元素 A 并在 B 中为它进行 bin-search 相关元素
- 那么是的，最差的复杂度是 O(m.log(n))
- 但也是最好的，因为你遍历了 b 的整个数组而不使用最后找到的索引
- 顺便说一句，如果你要解析 B 并搜索 A，那么 O(n.log(m)) 更好，如果 m>n
您的公共元素计算代码令人困惑
- 为什么会有if (i<n)???
- 如果你有 A={1,2,3,4,5} 和 B={3,5} 怎么办？
- 那么这个 if 将拒绝两个公共元素
- 我的意见是应该删除
- 所以在删除之后，所有情况下的复杂度都是 O(m.n)

[edit1] 代码更新以处理边缘情况

int c=0; // common elements
if (n+m) for (int i=0,j=0;;) // loop only if both arrays are not empty
 {
      if (a[i]==b[i]) { c++; if (i<m-1) i++; else if (j==n-1) break; j++;  }
 else if (a[i]< b[i]) {      if (i<m-1) i++; else if (j==n-1) break; }
 else                 {      if (j<n-1) j++; else if (i==m-1) break; }      
 }

多重二进制搜索和比较算法的复杂性

Complexity of Multiple Binary Search and comparison algorithms

sorting

algorithm

big-o

search