Ordo - 计算 c 和 n₀
Ordo - Calculating c & n₀
我在这个作业中遇到了一些问题。我很难知道如何处理我收集的数据。
我的任务是计算 ordo 和 n₀ 中的常数 c。
我们有一个通过终端执行的未知代码。我们可以选择要处理多少元素。元素越多，程序运行时间越长运行.
在程序结束时，我们会得到一个关于程序完成所用时间的数字。
这是收集到的数据：
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₀ 吗？
一般来说，通过测量在不同输入上 运行 所花费的时间来 "compute" 函数的复杂性并不是一个好主意。
例如假设该函数使用大整数和大字符串各占 50%。现在你有了一个特殊的编译器扩展，可以极大地加速大整数运算。现在可能会错过 运行 时间与整数输入的关系。
如果您必须在没有函数源代码的情况下了解复杂性，您可以使用 运行 时间 t 作为 "complexity function" f(t ).要证明该函数在 O(n²) 中，您只需给出 g(t)、c 和 n₀，使得 f(t) ≤ c⋅g(t) 成立所有 t ≥ n₀, 不一定是精确的。
在您的情况下，可以选择 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¹⁰ 作为输入，这个结果也有可能是错误的。如果您想获得确切的复杂性，则必须查看代码。
我在这个作业中遇到了一些问题。我很难知道如何处理我收集的数据。
我的任务是计算 ordo 和 n₀ 中的常数 c。
我们有一个通过终端执行的未知代码。我们可以选择要处理多少元素。元素越多，程序运行时间越长运行.
在程序结束时，我们会得到一个关于程序完成所用时间的数字。
这是收集到的数据：
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₀ 吗？
一般来说，通过测量在不同输入上 运行 所花费的时间来 "compute" 函数的复杂性并不是一个好主意。
例如假设该函数使用大整数和大字符串各占 50%。现在你有了一个特殊的编译器扩展，可以极大地加速大整数运算。现在可能会错过 运行 时间与整数输入的关系。
如果您必须在没有函数源代码的情况下了解复杂性，您可以使用 运行 时间 t 作为 "complexity function" f(t ).要证明该函数在 O(n²) 中，您只需给出 g(t)、c 和 n₀，使得 f(t) ≤ c⋅g(t) 成立所有 t ≥ n₀, 不一定是精确的。
在您的情况下，可以选择 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¹⁰ 作为输入，这个结果也有可能是错误的。如果您想获得确切的复杂性，则必须查看代码。