我正在为一个运行时间为 O(n^3) 的函数计时，但我的计时结果并未显示这一点，为什么会这样？

Question

numberOfTrials = 10;
numberOfSizes = 6;
sizesArray = zeros(numberOfSizes, 1);

randomMAveragesArray = zeros(numberOfSizes, 1);

for i=1:numberOfSizes
    N = 2^i;
    %x=rand(N,1);

    randomMTimesArray = zeros(numberOfTrials, 1);

    for j=1:numberOfTrials
        tic;
        for k=1:N^3
                x = .323452345e-999 * .98989898989889e-953;
        end
        randomMTimesArray(j) = toc;
    end

    sizesArray(i) = N;

end

randomMPolyfit = polyfit(log10(sizesArray), log10(randomMAveragesArray), 1);
randomMSlope = randomMPolyfit(1);

那是我的 Matlab 脚本。我最初是使用'\'来解决一个NxN随机矩阵的问题。运行时间为 O(n^3)。但我的对数图斜率始终约为 1.8。

我对 this 的理解是计时结果为 O(n^k)，其中 k 是 log/log 图中的斜率。因此，我应该得到的斜率应该在 3 左右。

我在上面发布的代码中，我创建了一个 N^3 的任意循环，并使用浮点运算来测试它是否有效。

但是对于 for 循环，我得到的斜率为 2.5。

这是为什么？

Answer 1

由于 O() 行为是渐近的，您有时看不到小 N 值的行为。例如，如果我设置 numberOfSizes = 9 并丢弃多项式拟合的前 3 个点，斜率更接近 3:

randomMPolyfit = polyfit(log10(sizesArray(4:end)), log10(randomMAveragesArray(4:end)), 1);
randomMSlope = randomMPolyfit(1)

randomMSlope =

          2.91911869082081

如果绘制时序数组，此行为会更清楚。

我正在为一个运行时间为 O(n^3) 的函数计时，但我的计时结果并未显示这一点，为什么会这样？

I'm timing a function that has a runtime of O(n^3) but my timing results do not show this, why is this happening?

big-o

matlab

time-complexity