我刚刚开始学习大 O 概念。我学到的是，如果函数 f 小于或等于函数 g 的另一个常数倍数，则 f 为 O(g)。
现在我遇到了一个示例，其中大小为“n”的字符串采用“2n”（输入大小的两倍）算法步骤。所以他们说所花费的时间是 O(2n)，但是他们按照这个说法说 As O(2n)=O(n)，时间复杂度是 O(n)。
我不明白这一点。由于 2n 总是大于 n，那么我们怎么能忽略 2 的倍数呢？任何小于或等于 2n 的都不一定小于 n！
这是否意味着我们在某种程度上将 n 和 2n 等同起来？听起来很混乱。请以最简单的方式澄清，因为我只是这个概念的初学者。此致 ：）
Big-O and related notations are intended to capture the aspects of algorithm performance that are most inherent to the algorithm, independent of how it is being run and measured.
Constant multipliers depend on the unit of measurement, seconds vs. microseconds vs. instructions vs. loop iterations. Even measured in the same units they will be different if measured on different systems. The same algorithm may take 20n instructions in one instruction set, 30n instructions on another. It may take 0.5n microseconds on one, 10n microseconds on another.
Many of the basic algorithm complexities you will see in the literature were calculated decades ago, but remain meaningful across significant changes in processor architecture and even more significant changes in performance.
Similar considerations apply to start-up and similar overheads.
A f(n) is O(n) if there exist constants N and c such that, for all n>=N, f(n) <= cn. For f(n) = 2n the constants are N=0 and c = 2. The first constant, N, is about ignoring overhead, the second, c, is about ignoring constant multipliers.
... As 2n will always be greater than n, how can we ignore the multple of 2 then? ...
Simply put, with growing n the multiplier loses its importance. The asymptotic behavior of a function describes what happens when n gets large.
Maybe it helps to consider not just O(n) and O(2n), because they are in the same class, but to contrast it with some other common classes. Example: Any O(n^2) algorithm will take longer than any O(n), in the long run (in the short run, their running times might even be reversed). Say you have two algorithms, one with linear time complexity of 100n and another with 8n^2. The quadratic algorithm will be faster for all n =< 12, but slower for all n > 12.
This property – that for any fixed nonnegative c and d you'll find an n, so that cn < dn^2 – constitues a part of the hierarchy of time complexities.
正如您在第一段中提到的那样，执行算法所需的时间与输入大小的恒定倍数成正比。您可以将 O(n) 视为 O(C*n)，其中 C 是任何常数乘数。