java - 根据步数确定时间复杂度

Question

一个类文件中有四种不同的算法，它们都有一定的时间复杂度。下面的输出是给定大小为 n 的随机数据的每个排序所花费的步骤数。我能得到一些关于如何确定时间复杂度的帮助吗？如果其中一种具有 n^2 的时间复杂度，我很确定我必须计算步数并除以 n^2 并查看它接近哪个数字，但我不确定该怎么做在那之后。希望我的问题不是太宽泛。

谢谢!

The array size is 100
Number of steps for Sort 1:         2543 
Number of steps for Sort 2:          813 
Number of steps for Sort 3:       495100 
Number of steps for Sort 4:          776 
The array size is 200
Number of steps for Sort 1:        10381 
Number of steps for Sort 2:         1870 
Number of steps for Sort 3:      3980200 
Number of steps for Sort 4:         1764 
The array size is 300
Number of steps for Sort 1:        20755 
Number of steps for Sort 2:         2999 
Number of steps for Sort 3:     13455300 
Number of steps for Sort 4:         2826 
The array size is 400
Number of steps for Sort 1:        40298 
Number of steps for Sort 2:         4244 
Number of steps for Sort 3:     31920400 
Number of steps for Sort 4:         3933 
The array size is 500
Number of steps for Sort 1:        65165 
Number of steps for Sort 2:         5448 
Number of steps for Sort 3:     62375500 
Number of steps for Sort 4:         5028 
The array size is 600
Number of steps for Sort 1:        90241 
Number of steps for Sort 2:         6697 
Number of steps for Sort 3:    107820600 
Number of steps for Sort 4:         6178 
The array size is 700
Number of steps for Sort 1:       122291 
Number of steps for Sort 2:         8030 
Number of steps for Sort 3:    171255700 
Number of steps for Sort 4:         7416 
The array size is 800
Number of steps for Sort 1:       157374 
Number of steps for Sort 2:         9053 
Number of steps for Sort 3:    255680800 
Number of steps for Sort 4:         8627 
The array size is 900
Number of steps for Sort 1:       202401 
Number of steps for Sort 2:        10674 
Number of steps for Sort 3:    364095900 
Number of steps for Sort 4:         9842 
The array size is 1000
Number of steps for Sort 1:       243032 
Number of steps for Sort 2:        12047 
Number of steps for Sort 3:    499501000 
Number of steps for Sort 4:        11101 
> 

Answer 1

这方面的标准技巧是在对数对数图上绘制值。

如果你有关系 y=A n^k 那么 log(y) = log(A) + k log(n) 你可以看到顺序只是直线的斜率。

例如，这是第一组数据的 log(n) log(v) 图:

这表明 k=2 的值 - 所以您的数据可能是 O(n^2)。

图片是用octave生成的

> n= [ 100, 200, 300, 400, 500, 600, 700, 800, 900, 1000 ]
> v = [2543, 10381, 20755, 40298, 65165, 90241, 122291, 157374, 202401, 243032]
> plot(log(n), log(v))

使用适当的线性拟合可以做出更好的估计。

使用

可以获得更高准确度的订单估计

> polyfit(log(n), log(v), 1)
ans =
    1.9892  -1.3227

这表明曲线大约为 v = 0.27 n^2，因为 exp(-1.3) 大约为 0.27。

值得注意的是，这只会让你得到 O(n^p log^q n) 类型行为中的 p 项，并且曲线会在顶部弯曲在那些情况下。