证明 O(n) 不是 O(n log n) 的子集
Prove O(n) is not a subset of O(n log n)
我在这个 post => Which algorithm is faster O(N) or O(2N)? 中看到 O(2n) 与 O(n) 相同的证明
这意味着 O(n) 与 O(4n) 相同。
谁能告诉我 O(n) 为什么不是 O(n log n) 的子集？
因为，如果 n = 16 且 base = 2，O(n log n) 将是 O(n * 4)，这应该使它成为 O(n)?
我知道上面的说法是错误的。但不确定是哪一部分。请澄清。
你不能说n=16。然后你把它当作一个常数。 n 是一个变量。
看看 O(n²)。如果n=16，则O(n²)=O(16*n)=O(256)=O(1)
它适用于任何复杂性。考虑 O(n!)，因为它适用于旅行推销员。如果n=16，则O(n!)=O(16!)=O(大常数)=O(1)
此外，正如 chepner 指出的那样，O(n) 是 O(nlog n) 的子集。您真正的问题是集合 O(n) 和 O(nlog n) 是否相等，但它们不相等。
Because, if n = 16 and base = 2, O(n log n) will be O(n * 4), which should make it O(n)?
这是对 O(n log n) 含义的根本误解。
O(n log n) 是 函数集 。直观上，它是所有函数 {g(n)} 的集合，其中 g(n) 与 f(n) = n log n 成正比。
（"proportional" 有严格的数学定义，处理尴尬的边缘情况，但你需要理解 "limits" ......这是相对高级的数学......才能理解定义。）
您正在用一个值代替参数...这在数学上毫无意义。从表面上看，您正在 评估 O(n log n) 作为某个 n 值的函数。如果 O(...) 表示一个函数，这可能有意义。但事实并非如此。
Big O 是一个数学符号，表示一组以特定方式与给定函数相关的函数。并且（直观地）关系是关于 n 变大时会发生什么。您可以用特定值替换 n 并仍然保留符号的含义。
（你所做的与取消 x 中的
一样具有数学意义
d(x.x)
------
dx
... 或那些小学生之一 "proofs" 一个是零，需要除以零。）
要更深入地了解为什么您的替换毫无意义，请查看 Big Oh 表示法的更正式定义；例如在 Wikipedia 上。如果你知道什么是限制。
我在这个 post => Which algorithm is faster O(N) or O(2N)? 中看到 O(2n) 与 O(n) 相同的证明 这意味着 O(n) 与 O(4n) 相同。
谁能告诉我 O(n) 为什么不是 O(n log n) 的子集？
因为，如果 n = 16 且 base = 2，O(n log n) 将是 O(n * 4)，这应该使它成为 O(n)?
我知道上面的说法是错误的。但不确定是哪一部分。请澄清。
你不能说n=16。然后你把它当作一个常数。 n 是一个变量。
看看 O(n²)。如果n=16，则O(n²)=O(16*n)=O(256)=O(1)
它适用于任何复杂性。考虑 O(n!)，因为它适用于旅行推销员。如果n=16，则O(n!)=O(16!)=O(大常数)=O(1)
此外，正如 chepner 指出的那样，O(n) 是 O(nlog n) 的子集。您真正的问题是集合 O(n) 和 O(nlog n) 是否相等，但它们不相等。
Because, if n = 16 and base = 2, O(n log n) will be O(n * 4), which should make it O(n)?
这是对 O(n log n) 含义的根本误解。
O(n log n) 是 函数集 。直观上，它是所有函数 {g(n)} 的集合，其中 g(n) 与 f(n) = n log n 成正比。
（"proportional" 有严格的数学定义，处理尴尬的边缘情况，但你需要理解 "limits" ......这是相对高级的数学......才能理解定义。）
您正在用一个值代替参数...这在数学上毫无意义。从表面上看，您正在 评估 O(n log n) 作为某个 n 值的函数。如果 O(...) 表示一个函数，这可能有意义。但事实并非如此。
Big O 是一个数学符号，表示一组以特定方式与给定函数相关的函数。并且（直观地）关系是关于 n 变大时会发生什么。您可以用特定值替换 n 并仍然保留符号的含义。
（你所做的与取消 x 中的
d(x.x)
------
dx
... 或那些小学生之一 "proofs" 一个是零，需要除以零。）
要更深入地了解为什么您的替换毫无意义，请查看 Big Oh 表示法的更正式定义；例如在 Wikipedia 上。如果你知道什么是限制。