0

我对编程相当陌生，最近被介绍到渐近复杂性的主题。我很好奇的是，考虑到元素的数量和对它们进行排序所花费的时间，如何计算排序方法的渐近复杂度。

这是我的意思的一个例子。

  • 'sortArray' 对具有 400 个元素的排序数组进行排序的时间：4
  • 'sortArray' 对具有 800 个元素的排序数组进行排序的时间：8
  • 'sortArray' 对具有 1600 个元素的排序数组进行排序的时间：16

  • 'sortArray' 对具有 3200 个元素的排序数组进行排序的时间：26

  • 'sortArray' 对具有 400 个元素的随机数组进行排序的时间：255

  • 'sortArray' 对具有 800 个元素的随机数组进行排序的时间：958
  • 'sortArray' 对具有 1600 个元素的随机数组进行排序的时间：4059
  • 'sortArray' 对具有 3200 个元素的随机数组进行排序的时间：16585

有关如何计算此类事物的 Big O 表示法的任何帮助？谢谢！

4

1 回答 1

2

根据定义，算法的渐近复杂度表示随着输入大小的增加（时间、空间或其他资源）的增长率。最好分析算法本身以确定这个增长率。但是，如果您只有一个“黑盒”排序算法，并且您只知道输入的大小和结果时间，那么您能做的最好的事情就是检查输入与时间的关系图是否在特定功能的模式。

为了测试这个想法，图形函数如下：

  • f(n) = n
  • f(n) = n ln n
  • f(n) = n^2

等等，看看哪个最像你创建的运行算法的时间图。请记住，渐近分析最终会忽略每个项的常数因子和任何低阶项。因此，即使图形看起来像 f(n) = 2n，如果您的算法仍然在线性时间内运行，那么您仍然有一个 O(n) 算法。

于 2010-09-28T18:34:42.783 回答