c++ - 计算插入排序和归并排序的效率(daa)

Question

假设 CPU 每秒可以处理 10^8 次操作。假设您必须对包含 10^6 个元素的数组进行排序？

插入排序和合并排序所花费的时间是多少小时？

想知道如何计算时间。

Answer 1

所提供的信息不足以给出问题的准确答案。

所花费的时间取决于数据本身和算法的实现。

当然，可以根据合理的假设进行估计。

插入排序是 O(n^2) ，所以它将按 K1 * 10^12 的顺序排列。对数组进行排序的操作，或 K1 * 10^4秒。即使采用优化的实现，插入排序也可能需要几个小时。

归并排序为O(n * log n) ，所以它将按 K2 * 10^6 * 6 的顺序排列。对数组进行排序的操作，或 K2 * 6 * 10^(-2)秒。合并排序可能需要不到一秒的时间。

这个例子很好地说明了为什么为工作选择正确的算法很重要。