根据运行时确定程序的时间复杂度(Determine time complexity of program based on its runtime)

根据运行时确定程序的时间复杂度(Determine time complexity of program based on its runtime)

我正在寻找一种基于运行时确定程序时间复杂度的方法。

我已经为不同大小的n绘制了我的结果，现在正在寻找一种方法来确定常数c和n0，使得每个n≥n0的f（n）≤c*（g（n））。

关于该计划：

输入：n，元素数量

输出：运行时间

测量数据的所有步骤都已完成100次，以获得程序的平均运行时间。

n的不同大小的一些示例值：

Ñ...............运行时（ms）的

1000 ......... .1,6

10 000 ...... .222,8

100 000 ...... 25213

非常感谢！

pepefatha

I'm looking for a way to determine the time complexity of a program based of its runtime.

I have plotted my results for different sizes of n and now looking for a way to determine the constants c and n0 so that f(n) ≤ c*(g(n)) for every n ≥ n0.

About the program:

Input: n, number of elements

Output: running time

All steps in measuring the data have been done 100 times to get an average runtime for the program.

Some example values for different sizes of n:

n……………runtime(ms)

1000……….1,6

10 000……..222,8

100 000……25213

Help much appreciated!

pepefatha

最满意答案

您肯定需要更多数据点。 但它看起来像你的n乘以10，大约将你的运行时间乘以100，所以n ^ 2将是我的猜测。

至于常数，你只需要在对数刻度上绘制它并找到截距（从最大值外推，即大于n0值的截距）和y轴，即log（c）。

You definitely need more data points to be sure. But it looks like multiplying your n by 10, approximately multiplies your runtime by 100, so n^2 would be my guess.

As for the constant, you just need plot it on a log scale and find the intercept (extrapolated from the largest values, i.e. those greater than the value of n0) with the y axis, which will be log(c).