指针在一次迭代中自增两次的函数的大0

Question

那么考虑一下必须找到链表中点的问题。一种解决方案是遍历列表，找到它的长度，然后找到中间的元素。另一个解决方案是有一个快速指针和一个慢速指针。我直观地觉得，第二种方法有一个O(n/2)，但不是快速指针访问其下一个节点之前去下一个->下一个节点?

这两种方法的O()是多少?大o和运行时之间有什么区别吗?

Answer 1

在比较算法时，明确我们要比较的是什么是有帮助的。以下是这两种算法的实现，它们是专门为方便计数指令而编写的。

第一个是这样的:

length := 0
node := first
repeat {
    if node == null { break }
    node = node->next
    length += 1
}
middle := first
length = (length - 1) / 2
repeat {
    if length == 0 { break }
    middle = middle->next
    length -= 1
}

第二个是这样的:

fast := first
slow := first
repeat {
    if fast == null { break }
    fast = fast->next
    if fast == null { break }
    fast = fast->next
    slow = slow->next
}

两种算法执行完全相同的空检查次数和完全相同的->next间接次数。

第一个算法对length进行N + 2 + (N/2)*2(近似2N)的算术运算。

两种算法的运行时间差异可能很小。虽然第一种算法做了额外的整数运算，但在现代机器上，->next所需的内存访问占主导地位，这在两种实现中是相同的。

运行时的复杂性是相同的。第一个执行额外的O(N)个整数操作，但两者总体上都是O(N)个。

Answer 2

两种方法的最坏情况时间复杂度均为O(n)。唯一的区别是在大列表的情况下，第一个算法将需要两次传递(第一次查找LinkedList的长度，第二次查找中间元素)。正式表示时间复杂度:

。e时间复杂度= O(n) + O(n/2) ~= O(n)

第二个算法是单遍算法，你可以在第一次遍历后找到中间元素。你的直觉认为第二个算法有O(n/2)是不正确的。虽然你的快速指针只访问n/2个元素，但它仍然是输入长度的线性函数。O(n/2) ~= O(n)

Time complexity = O(n).

对于较大的列表，避免第二次遍历将导致更快的执行。但是大O符号的整体思想是将时间复杂度表示为输入大小的增长函数而忽略其他细节。