假设CPU每秒可以处理10 ^ 8次操作。假设您必须对具有10 ^ 6个元素的数组进行排序？
hr中插入排序n合并排序所花费的时间是什么？
想知道如何计算时间。
最佳答案
所提供的信息不足以给出对该问题的准确答案。
所花费的时间将取决于数据本身和算法的实现。
当然，可以基于合理的假设进行估算。
插入排序为O(n^2)，因此需要按K1 * 10^12操作的顺序对数组进行排序，即K1 * 10^4秒。即使使用优化的实现，插入排序也可能要花费几个小时。
合并排序为O(n * log n)，因此需要按K2 * 10^6 * 6操作的顺序对数组进行排序，即K2 * 6 * 10^(-2)秒。合并排序可能需要不到一秒钟的时间。
这个例子很好地说明了为什么为工作选择正确的算法很重要。