0

对不起，我在之前的问题中犯了一个错误。因此，我没有得到我想要的答案。

老师告诉我们，每次除以 2 时，运行时间很可能是 log n。例如，如果我们将一个数组一分为二，每次遍历其中一个数组时，运行时间将是 log n。但是，我们可能会遇到 LinkedList 很容易被误导的情况。例如，我们可能有一个算法，通过从头部或尾部开始将列表的第 n 个元素设置为其他元素，以使运行时间小于 n。从逻辑上讲，我们可能认为运行时间是 log n，但事实并非如此。这是为什么？你如何确定？

我们是否需要绝对拆分才能获得 log n 的运行时间？当循环的最大运行时间为 n/2 时，我认为说 n 的运行时间没有任何逻辑意义。

4

1 回答 1

0

我认为这里有些概念需要稍微提炼，因为时间复杂度只与算法有关，与您正在操作的数据结构的大小无关。

老师告诉我们，每次除以 2 时，运行时间很可能是 log n。例如，如果我们将一个数组一分为二，每次遍历其中一个数组时，运行时间将是 log n。

现在，遍历一个数组，比如

for (int i = 0; i < array.size; i++) {
    variable = array[i];
}

运行O(n)：执行此类操作所需的时间随数组的大小线性变化。您将拥有O(log n)像对数组进行二进制搜索这样的操作，但您不能将此概念推广到所有数组操作，尤其是那些需要遍历数组的操作。

现在，这句话

例如，我们可能有一个算法，通过从头部或尾部开始将列表的第 n 个元素设置为其他元素，以使运行时间小于 n。

让我相信您认为大 O 中使用的 n 与您所谓的“第 n 个元素”直接相关。他们不是。在链表上，您唯一的选择元素 n 是转到列表的开头并沿着您要查找的元素的链接（或者在双链表的情况下，转到开头或结尾取决于您要查找的元素的位置），因此此操作的时间复杂度为 O(n)，即与集合的长度线性相关。

于 2013-05-24T16:22:08.183 回答