时间戳

首页 > 解决方案 > 基于数组中的最大数量迭代的算法的复杂性？

arrays - 基于数组中的最大数量迭代的算法的复杂性？

问题描述

所以我正在做一个朋友向我提议的竞争性编程挑战，我能够弄清楚，但在那之后，我决定用其他方法来解决它。

问题是，我确实找到了一种奇怪的方法，但我们无法真正理解复杂性，因为我们认为它可能没有正式的复杂性？

问题的简要说明如下：

你有一个整数数组（可能没有排序），都是正数且大于 0。

你的任务是告诉我数组中缺少的第一个整数，例如：

[1, 4, 5,3, 2, 6, 10] ==> 答案是 7

我的有趣做法是：

您遍历数组一次，并将所有值放入 HashMap 中，将数组中的最大值保存在单独的变量中。

之后，您创建一个从 1 到数组最大值的 for 循环。

然后检查哈希图中是否存在 for 循环索引，如果不存在，则您已找到答案。

问题是，这将是 O(n)，但是 for 循环有点搞砸了。是 O(n) 吗？说 O(n) 感觉不对。

想象一下这个伪代码：

让 numArray = {1, 2, 3, 1000};

for i=1 TO max(numArray){
     print "Hello there buddy"
}

这会有什么复杂性？它甚至有形式上的复杂性吗？

根据我的理解，说它具有复杂性并没有真正遵循 Big O 表示法的目的，因为它的目的是评估运行某些代码所需的时间，输入更改的大小，在这里输入的大小无关紧要，只要最大数的值...如果数组有 3 个元素，最大值为 10 亿，它仍然需要 10 亿次迭代...

那么，有没有一个具体的符号呢？

你会如何描述这个问题？

标签： arraystime-complexity

解决方案

在这种情况下，我们假设一个新变量 m 并说这个解是O(m)，其中 m 将是数组中的最大数；而不是说O(n)。

只是一个额外的输入，解决这个问题的另一种更好的方法如下：

认为

a = [1, 4, 5,3, 2, 6, 10]
for i in 0->n:
  if (a[i] < n)
    a[a[i]] = -a[a[i]];

for i in 0->n:
  if (a[i] > 0)
    print (i);

基本上这里的想法是通过将其符号反转为 -ve 来标记访问过的索引。重新迭代第一个找到的正元素的索引将是丢失的项目。

推荐阅读