与Big O有点混淆

Question

因此，我有一个关于如何验证函数的大O的快速问题。

例如:快速排序算法对包含5000000个元素的数组进行排序会产生0.008524秒的时间间隔，对1000000个元素运行相同的算法会产生0.017909个元素。如果我的快速排序是/不是n*log(N)的大O，我如何检查大O？

我想我理解的是:n增加了2，因此运行时间应该增加2*log(2)？

f(n) = 0.008524 -> n log (n)

f(2n) = 0.017909 ->2n*log(2n)

Answer 1

大O符号是渐近的。这意味着当n变大时，它只适用于限制。

用50和100个元素排序可能无法跟踪O(n log n)的原因有很多，缓存效果可能是一个候选因素。如果你尝试了100,000,200,000和100,000，你可能会发现它的轨迹会更好一点。

另一种可能性是，大多数快速排序实现平均只有O(n log n)；一些输入将花费更长的时间。对于50个元素，遇到这样的病理输入的几率比对于100,000个元素的概率更高。

不过，最终，您并不是“验证”大O运行时；而是根据算法所做的来证明它。

Answer 2

大O表示法通常与以秒为单位的运行时间无关。它与算法执行的操作的数量有关。建立这种关系的唯一方法是查看函数的代码。

不仅运行时会受到低阶项的影响(请记住，大O符号只关注最高阶项)，还会影响程序启动开销、缓存效率和分支预测等因素。

话虽如此，在您的情况下，这些其他影响可能都不会显着。在这种情况下，如果n加倍，那么运行时间将从k.n.log(n)增加到k.2n.log(2n) = k(2n.log(2) + 2n.log(n))。

Answer 3

有几点需要牢记:首先也是最重要的是，当你改变大小时，硬件(至少在典型的计算机上)也会产生影响。特别是，当您的数据变得很大，无法容纳特定大小的缓存时，您可能会看到运行时的大幅跳跃，这与所讨论的算法完全无关。

为了更好地理解算法本身，你应该(可能)从比较一些具有非常明显的复杂性的算法开始，但使用相同大小的数据。一种明显的可能性是，计算用随机数填充数组所需的时间。至少假设一个相当典型的PRNG，这当然应该是线性的。

然后计算算法的时间，看看它相对于相同大小的线性算法是如何变化的。例如，您可以使用如下代码：

#include <vector>
#include <algorithm>
#include <iostream>
#include <time.h>
#include <string>
#include <iomanip>

class timer { 
    clock_t begin;
    std::ostream &os;
    std::string d;
public:
    timer(std::string const &delim = "\n", std::ostream &rep=std::cout) 
        : os(rep), begin(clock()), d(delim)
    {}
    ~timer() { os << double(clock()-begin)/CLOCKS_PER_SEC << d; }
};

int main() { 
    static const unsigned int meg = 1024 * 1024;

    std::cout << std::setw(10) << "Size" << "\tfill\tsort\n";
    for (unsigned size=10000; size <512*meg; size *= 2) {
        std::vector<int> numbers(size);
        std::cout << std::setw(10) << size << "\t";
        { 
            timer fill_time("\t");
            std::fill_n(numbers.begin(), size, 0);
            for (int i=0; i<size; i++)
                numbers[i] = rand();
        }
        {
            timer sort_time;
            std::sort(numbers.begin(), numbers.end());
        }
    }
    return 0;
}

如果我用图表表示填充时间和排序时间，得到的结果如下所示：

​

​

因为我们的大小是指数的，所以我们的线性算法显示(大致)指数曲线。排序的时间显然还在增长(有些)。

编辑:公平地说，我可能应该补充说，log(N)增长非常缓慢，对于几乎任何实际数据量，它的贡献都很小。对于大多数实际目的，您可以将快速排序(例如)视为大小的线性排序，只是使用比填充内存更大的常量因子。线性增加大小并绘制结果会使这一点变得更加明显：

​

​

如果你仔细观察，你可能会看到上面的线显示了从"log(N)“因子开始的一条略微向上的曲线。另一方面，如果我不知道它应该在那里，我不确定我会注意到任何曲率。