我知道n 2是多项式。对数算法很快。但我对不同的数据输入感到困惑。小投入和大投入的情况是什么？
例如，假设您有两种排序算法：
B 是 O(n 2 )，Q 是 O(n lg n)。
Q总是比B快吗？请提供您对这两种情况的想法。
问问题
695 次
2 回答
2
大 O 表示法隐藏了一个乘法常数，因此对于一些小的 n 值，O(n^2) 算法可能更快。
大 O 只是保证在 x 的某个输入大小之后，具有较低增长率的算法将在更短的时间内运行（我假设我们正在做 O 时间，但它也可以指空间或其他因素）。
于 2013-04-30T00:32:29.037 回答
1
n^2 是多项式 - 2^n 是指数
Big-oh 处理渐近复杂性，这意味着当“n”很大时；所以你的问题的答案是“错误的”。如果 O(n^2) 算法的精确运行时间为 n^2，而 O(n lg n) 算法的精确运行时间为 10 * n lg n，那么对于小 n，n^2算法会更快（例如，n = 5; 5 ^ 2 = 25, 10 * 5 * lg(5) 约为 100）。然而，对于较大的 n，“10*”因子是无关紧要的。
有时一个算法会结合两个或多个算法来利用这一点；例如，插入排序是 O(n^2)，但有一个小的常数因子，而合并排序是 O(n lg n)，有一个较大的常数因子，所以当合并排序将其子数组拆分成足够小的块时，它将对它们使用插入排序。
于 2013-04-30T00:32:52.693 回答