c - Ordo-计算c＆n₀

我有这个作业，但遇到一些问题。我很难知道如何处理我收集的数据。

我的任务是计算ordo中的常数c以及n₀。

我们有一个未知的代码，可以通过终端执行。我们可以选择要处理的元素数量。元素越多，程序运行所需的时间就越长。

在程序结束时，我们会得到一个数字，说明该程序需要多长时间才能完成。

这是收集的数据：

Input   |  time (s)
--------+----------
1000    |   0.0015
1000    |   0.0016
1000    |   0.0015
2000    |   0.0063
2000    |   0.0063
3000    |   0.0063
4000    |   0.0281
4500    |   0.0344
5000    |   0.0453
6000    |   0.0672
7000    |   0.0953
8000    |   0.1265
9000    |   0.1656
10000   |   0.2078
11000   |   0.2547
12000   |   0.3062
15000   |   0.4875
20000   |   0.8953
25000   |   1.4125
30000   |   2.0390
35000   |   2.8750
40000   |   3.6641
50000   |   5.7641
50000   |   5.7438
70000   |   11.4781
75000   |   13.7312
80000   |   15.0828
85000   |   17.1156
90000   |   19.8610
100000  |   23.2328
110000  |   28.8032
130000  |   40.6344

问题是：我如何从这里继续前进？我想看看图表告诉我，复杂度为O（n²）。

我有什么技巧可以进行下一步并计算c＆n₀？

最佳答案

通常，通过测量在不同输入上运行所花费的时间来“计算”函数的复杂性不是一个好主意。

例如。可以说该函数使用大整数和大字符串，每个字符串占50％。现在，您有一个特殊的编译器扩展，可以大规模加速大整数运算。现在可能会错过运行时如何使用整数输入进行缩放。

如果您必须在没有函数源代码的情况下了解复杂性，则可以使用运行时t作为“复杂性函数” f（t）的输入。为了证明函数在O（n²）中，您只需要给出g(t)，c和n₀，使得对于所有t≥n₀，f（t）≤c⋅g（t）成立，不一定是准确的。

在您的情况下，可以选择g(t) = t² + 1，c = 1和n₀ = 0。
您还可以将g(t) = 1/4⋅10⁻⁸⋅t²+1与c = 1和n₀ = 0（红色）一起使用
或g(t) = 1/4⋅10⁻⁸⋅t²和c = 1和n₀ = 40000（蓝色）。



但请注意：您无法做到这一点。如果您测试10¹⁰作为输入，则此结果也有可能错误。如果您想获得确切的复杂性，则必须看一下代码。

关于c - Ordo-计算c＆n₀，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28015145/