在某些算法的时间复杂度中找到常量 c
Finding the constant c in the time complexity of certain algorithms
我需要帮助找到并逼近插入排序 (cn^2) 和归并排序 (cnlgn) 的复杂度中的常量 c，方法是检查其 运行 次的结果。
一些背景知识，我的目的是“实现插入排序和归并排序（降序）算法并测量这两种算法的性能。对于每个算法，对于每个 n = 100、200、300， 400, 500, 1000, 2000, 4000，当输入为
时测量它的运行时间
- 已经排序，即n, n-1, …, 3, 2,1；
- 反向排序 1, 2, 3, … n;
- 1, 2, …, n 的随机排列。
运行时间应该不包括初始化时间。"
我已经完成了两种算法的代码并将测量值（微秒）放入电子表格中。现在，由于每个算法的每个条件的值不同，我不确定如何找到这个 c。
供参考，时间table：
插入排序归并排序
n AS RS 随机 AS RS 随机
100 12 419 231 192 191 211
200 13 2559 1398 1303 1299 1263
300 20 236 94 113 113 123
400 25 436 293 536 641 556
500 32 504 246 91 81 105
1000 65 1991 995 169 246 214
2000 9 8186 4003 361 370 454
4000 17 31777 15797 774 751 952
如果需要我可以提供代码。
几乎不可能确定这些常量的值，尤其是对于使用高速缓存、管道和其他 "performance things" 的现代处理器。
当然，您可以尝试找到一个近似值，然后您将需要 Excel 或任何其他电子表格。
输入您的数据，创建图表，然后添加趋势线。电子表格会为您计算常数值。
首先是一些注意事项：
你有很小的n
算法复杂度只有在n足够大的情况下才开始对应运行时间。因为 n=4000 是 ~4KB 的数据，它仍然可以放入大部分 CPU 缓存的 所以增加到至少 n=1000000 可以而且将会显着改变运行时和 n 之间的关系 !
运行时测量
对于随机数据，您需要平均运行时间测量而不是单个测量，因此对于任何 n 至少使用不同的数据集进行 5 次测量，并使用所有
的平均时间
现在如何获取c
如果程序具有复杂性 O(n^2) 这意味着对于足够大的 n 运行时间是：
t(n)=c*n^2
所以少做一些测量。我从你的插入排序中选择最后 3 个，反向排序，因为如果我没记错的话，它应该匹配最坏情况 O(n^2) 复杂度：
c*n^2 =t(n)
c*1000^2= 1.991
c*2000^2= 8.186
c*4000^2=31.777
求解方程：
c=t(n)/(n^2)
c= 1.991/ 1000000=1.991 us
c= 8.186/ 4000000=2.0465 us
c=31.777/16000000=1.9860625 us
如果一切正常，那么不同 n 的 c 应该是相对相同的。在您的情况下，每个元素大约 2 us 但正如我上面提到的那样，随着 n 的增加，这将由于 CACHE 的使用而改变。此外，如果使用任何动态容器，那么您必须将其使用的复杂性包含在算法中，这有时可能很重要！！！
首先要理解的是，复杂度和运行宁次是不一样的，可能没有很彼此关系密切。
复杂性 是一种理论测量，用于了解算法在 较大 输入上与较小输入相比如何变慢或比较到其他算法。
运行ning 时间 取决于确切的实现，运行ning 所在的计算机，运行 的其他程序在同一台计算机和许多其他东西上。您还会注意到，如果输入对您的缓存来说太大，运行ning 时间会变慢，如果输入对您的 RAM 也太大，则跳转另一个时间。如您所见，对于 n = 200，您得到了一些奇怪的 运行ning 次。这不会帮助您找到常量。
在没有代码的情况下，您别无选择，只能使用 运行ning 时间来近似计算复杂度。那么你应该只使用大输入（1000 应该是你的情况下的最小输入）。如果您的算法是确定性的，只需输入最坏的情况。随机案例有好有坏，因此您永远无法了解真正的复杂性。另一个问题是，复杂度测量 "operations"，因此评估和 if 语句或递增变量是相同的，但在 运行 宁时间内 if 需要更多时间比递增的东西。
所以你可以做的是绘制你的复杂性和你测量的值，并寻找一个持有的因素......
例如这是 n² 由 1/500 和您图表中的点组成的图表。
以 4000 个元素为例，将时间除以相应的复杂性估计，4000² 或 4000 Lg 4000。
这并不比任何其他方法差。
为了安全起见，您无论如何都应该检查最后的值是否在相对平滑的曲线上对齐，以便 4000 的值具有代表性。
正如其他人评论的那样，这是一种相当糟糕的方法。你还应该考虑运行次的标准差，或者更好的是，运行次的直方图，覆盖更大的尺寸范围。
另一方面，获得准确的值并不重要，因为知道常量的值对比较两种算法没有帮助。
我需要帮助找到并逼近插入排序 (cn^2) 和归并排序 (cnlgn) 的复杂度中的常量 c，方法是检查其 运行 次的结果。
一些背景知识，我的目的是“实现插入排序和归并排序（降序）算法并测量这两种算法的性能。对于每个算法，对于每个 n = 100、200、300， 400, 500, 1000, 2000, 4000，当输入为
时测量它的运行时间- 已经排序，即n, n-1, …, 3, 2,1；
- 反向排序 1, 2, 3, … n;
- 1, 2, …, n 的随机排列。
运行时间应该不包括初始化时间。"
我已经完成了两种算法的代码并将测量值（微秒）放入电子表格中。现在，由于每个算法的每个条件的值不同，我不确定如何找到这个 c。
供参考，时间table：
插入排序归并排序
n AS RS 随机 AS RS 随机
100 12 419 231 192 191 211
200 13 2559 1398 1303 1299 1263
300 20 236 94 113 113 123
400 25 436 293 536 641 556
500 32 504 246 91 81 105
1000 65 1991 995 169 246 214
2000 9 8186 4003 361 370 454
4000 17 31777 15797 774 751 952
如果需要我可以提供代码。
几乎不可能确定这些常量的值，尤其是对于使用高速缓存、管道和其他 "performance things" 的现代处理器。
当然，您可以尝试找到一个近似值，然后您将需要 Excel 或任何其他电子表格。
输入您的数据，创建图表，然后添加趋势线。电子表格会为您计算常数值。
首先是一些注意事项：
你有很小的
n算法复杂度只有在
n足够大的情况下才开始对应运行时间。因为n=4000是~4KB的数据，它仍然可以放入大部分 CPU 缓存的 所以增加到至少n=1000000可以而且将会显着改变运行时和n之间的关系 !运行时测量
对于随机数据，您需要平均运行时间测量而不是单个测量，因此对于任何
的平均时间n至少使用不同的数据集进行 5 次测量，并使用所有
现在如何获取c
如果程序具有复杂性 O(n^2) 这意味着对于足够大的 n 运行时间是：
t(n)=c*n^2
所以少做一些测量。我从你的插入排序中选择最后 3 个，反向排序，因为如果我没记错的话，它应该匹配最坏情况 O(n^2) 复杂度：
c*n^2 =t(n)
c*1000^2= 1.991
c*2000^2= 8.186
c*4000^2=31.777
求解方程：
c=t(n)/(n^2)
c= 1.991/ 1000000=1.991 us
c= 8.186/ 4000000=2.0465 us
c=31.777/16000000=1.9860625 us
如果一切正常，那么不同 n 的 c 应该是相对相同的。在您的情况下，每个元素大约 2 us 但正如我上面提到的那样，随着 n 的增加，这将由于 CACHE 的使用而改变。此外，如果使用任何动态容器，那么您必须将其使用的复杂性包含在算法中，这有时可能很重要！！！
首先要理解的是，复杂度和运行宁次是不一样的，可能没有很彼此关系密切。
复杂性 是一种理论测量，用于了解算法在 较大 输入上与较小输入相比如何变慢或比较到其他算法。
运行ning 时间 取决于确切的实现，运行ning 所在的计算机，运行 的其他程序在同一台计算机和许多其他东西上。您还会注意到，如果输入对您的缓存来说太大，运行ning 时间会变慢，如果输入对您的 RAM 也太大，则跳转另一个时间。如您所见，对于 n = 200，您得到了一些奇怪的 运行ning 次。这不会帮助您找到常量。
在没有代码的情况下，您别无选择，只能使用 运行ning 时间来近似计算复杂度。那么你应该只使用大输入（1000 应该是你的情况下的最小输入）。如果您的算法是确定性的，只需输入最坏的情况。随机案例有好有坏，因此您永远无法了解真正的复杂性。另一个问题是，复杂度测量 "operations"，因此评估和 if 语句或递增变量是相同的，但在 运行 宁时间内 if 需要更多时间比递增的东西。
所以你可以做的是绘制你的复杂性和你测量的值，并寻找一个持有的因素......
例如这是 n² 由 1/500 和您图表中的点组成的图表。
以 4000 个元素为例，将时间除以相应的复杂性估计，4000² 或 4000 Lg 4000。
这并不比任何其他方法差。
为了安全起见，您无论如何都应该检查最后的值是否在相对平滑的曲线上对齐，以便 4000 的值具有代表性。
正如其他人评论的那样，这是一种相当糟糕的方法。你还应该考虑运行次的标准差，或者更好的是，运行次的直方图，覆盖更大的尺寸范围。
另一方面，获得准确的值并不重要，因为知道常量的值对比较两种算法没有帮助。