算法时间复杂度。

Question

如果我们第一次遍历整个链表(比方说单链表)，那么时间复杂度逐渐达到O(N)，其中n是no。如果我们重复它，有意义的是，没有。(比方说200)的时间，但我们仍然表示时间复杂度O(n)本身，那么我的问题是1。为什么我们不考虑上述两者之间的差异(因为第二个算法比第一个算法需要更多的时间)，并且我们表示相同的asymptotically.As，我们使用时间复杂度主要参数来比较算法之间的差异。

Answer 1

假设算法A是“遍历列表一次”。

假设算法B是“遍历列表200次”。

它们都是线性的，即它们的时间复杂度为O(n)。为什么？如果您将输入列表的大小加倍，

• 算法A需要的时间是以前的两倍，而B需要的时间是以前的两倍。

这就是线性时间背后的直觉。

你总是可以插入Big-O的正式定义来证明“遍历列表200次”在复杂性上是线性的(你知道，找到一个常数k，使得对于所有n>某些N，诸如此类)。渐近复杂性只关心特定算法在其输入大小增长时的行为。因此，我们不需要比较算法A和算法B来说明算法B的渐近时间复杂度。

Answer 2

O(n)提供了一个函数可以花费的最大时间的上限，因此，它们可能都花费了不同的时间，但它们的上限仍然是same.Big O符号，它根据函数的增长率来表征函数:具有相同增长率的不同函数可以使用相同的O符号来表示。