algorithm - 将 arraylist 转换为小于 O(n) 的数组

Question

我目前正在开发程序并希望将 ArrayList 转换为数组，但时间少于 O(n)。

  for (int i = 0; i < list.size(); i++) {




    if (list.get(i) != null) {
                                 arr[i] = list.get(i);
                             }
                     }

标签： algorithmarraylistdata-structures

Answer 1

如果 n 是列表的长度，那么 O(n) 意味着在这种情况下，您查看列表中的每个元素并复制它。
现在你说你想在小于 O(n) 的时间内转换它。这意味着您必须忽略列表中的某些元素。如果不是，它将再次是 O(n)。但是你忽略了哪个？请记住，您不允许查看所有其他元素，否则它将再次出现在 O(n) 中。
假设您知道该列表包含布尔值，其中 n/2 为真，其他为假。在最好的情况下，所有真实值都在列表的前半部分。现在您可以在列表的 n/2 处停止迭代，但您需要再次将错误值添加到您的数组中。现在你又在 O(n) 了。
让我们再做一个假设。您始终可以忽略列表的最后一个值。这意味着您只迭代 n-1 次，然后是 O(n-1) 但在大 O 表示法中，您忽略常量，因此它再次获得 O(n)。

不可能将列表的所有 n 个元素复制到低于 O(n) 的数组中。