-4

我已经编写了这段代码，但我必须找到大 O 表示法。我想出了 O(n2) 但我不确定它是否正确。请有人帮忙。谢谢

int n = array.length;

for(int i=0;i<array.length;i++){
  int c = 1;
  for(int j=i+1;j<array.length;j++)
    if (array[i]==array[j])
      c=c+1;
    if (c>(array.length/2)){
      return array[i];
    }
  }
  return 0;
}
4

2 回答 2

0

如果我们假设数组中没有 2 个相等的元素，它将等于最坏情况冒泡排序，它等于 O(N2)。您可能会在wikibooks中看到示例排序

并且还可以在此处找到有关冒泡排序成本的信息。

于 2013-02-26T23:28:30.067 回答
0

您是对的，这是一个 O(n^2) 操作，因为您执行的操作数量与输入数组中数据元素数量的平方成正比。

如果匹配数超过数组长度的一半，则您具有“救助”条件这一事实也不会改变操作的基数，它仍然是 N 平方操作，因为这是函数的限制行为。

验证这一点的一种方法是通过蒙特卡罗模拟：

  1. 从 N=2 开始，增加到 N= 说 100
  2. 在内部循环中添加第二个计数器，让您知道您点击内部代码块的次数
  3. 创建一个长度为 N 且只有二进制 (1/0) 值的随机数组
  4. 运行你的函数并记录你点击内循环的次数
  5. 对于 N 的每个选择，运行模拟 100 次，然后对每个 N 选择的结果取平均值
  6. 在对数尺度上绘制平均迭代次数与 N 的关系。
  7. 对数对数图上斜率为 2 的最佳拟合线表示操作为 O(N^2)。斜率为 1 意味着它是 O(N)。斜率为 3 表示 O(N^3)。
于 2013-02-26T23:56:22.790 回答