线性复杂度和二次复杂度

Question

3

我不确定...

如果你有一段可以在以下两种复杂度中执行的代码：

1. O(n) 的序列，比如：两个O(n)的顺序排列 2. O(n²)

则更喜欢能在线性时间内执行的那个版本。会不会有一个时刻，O(n)序列太多了，反而更喜欢O(n²)呢？换言之，对于任意常数C，语句C x O(n) < O(n²)是否总是成立？

为什么？有哪些因素会影响这个条件，使得选择O(n²)复杂度更好？

- jasonline

4个回答

2

如果您的常数C大于n值，则O(n²)算法会更好。

- Chris J

1

O符号中总是有一个隐含的常数，因此，对于足够小的n，O(n^2)可能比O(n)更快。如果O(n)的常数比O(n^2)的常数小得多，就会发生这种情况。

- Paul R

你的意思是反过来：O(n^2) 比 O(n) 更快。 - Andreas Brinck

0

C x O(n) < O(n²) 并不总是成立，存在一个 n 的点使得它反转了这个条件。

当 C 很大而 n 很小时，C x O(n) > O(n²)。然而，C 始终是常数，因此当 n 缩放到一个大数时，C x O(n) < O(n²)。

因此，当 n 很大时，O(n) 总是比 O(n²) 更好。

- TechTravelThink

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jk. · Accepted Answer

我认为这里有两个问题：首先是符号的含义，其次是在实际程序中你将会测量到什么。

1. 大O被定义为n趋近于无穷大时的极限，因此从大O的角度来看，O(n) < O(n^2)总是成立的，不考虑任何有限常数。

2. 正如其他人所指出的，在实际程序中只涉及一些有限的输入，因此很可能选择一个足够小的n值使得c*n > n^2，即c > n，然而严格地说，你不再涉及大O。