当 CPU 对 10^8 operations/sec 进行运算时，对数组进行排序所花费的时间
Time taken to sort array, when CPU operates on 10^8 operations/sec
假设一个CPU每秒可以处理10^8个操作。假设您必须对包含 10^6 个元素的数组进行排序。以下哪项是正确的？
- 插入排序总是需要 2.5 小时以上，而归并排序总是不到 1 秒。
- 插入排序总是需要 2.5 小时以上，而快速排序总是不到 1 秒
- 插入排序可能需要超过 2.5 小时，而归并排序总是需要不到 1 秒。
- 插入排序可能需要超过 2.5 小时，而快速排序总是需要不到 1 秒。
插入排序的最坏情况复杂度是多少？
合并排序和快速排序的最坏情况下的复杂度是多少？
有没有可能插入排序不到2.5小时？如果是，情况如何？
快速排序（或归并排序）的最佳复杂度是多少？
插入排序的最佳情况复杂度是多少？
如果你回答了这些问题。你会很容易回答你的问题。
如果您不知道什么是最坏情况或最佳情况，请尝试找到这些问题的答案。
如果排序需要 10^12 步，如果您的 CPU 每秒执行 10^8 步，排序会持续多少秒（或几小时）？
对长度为 n 的数组进行快速排序、归并排序或插入排序需要多少步？
回答以上所有问题会让您离回答您的问题更近一步。
去做吧，我保证，你马上就能回答。
插入排序和快速排序的最坏情况复杂度为 O(n^2)。
合并排序的最坏情况复杂度为 O(n*log(n))
因此，对于插入排序和快速排序没有。步骤数 (10^6)^2 = 10^12
所以需要 10^12/10^8 = 10^4 or 10,000 seconds = 2.77hrs（因为 CPU 运算 10^8 steps/sec）
哪里，没有。合并排序的步骤是 (10^6*log(10^6)) = 6*10^6 个步骤，需要 (6*10^6/10^8) = 0.06secs 个，小于 1
但视情况而定，选项 1 或 3 可能是正确的，此处插入排序可能需要不到 2.5 小时，具体取决于问题，因为插入排序的平均情况复杂度是 (N-1)*N/4 计算 运行 时间，我们得到 0.69hrs 小于 2.5 小时，所以第三个陈述是正确的。
假设一个CPU每秒可以处理10^8个操作。假设您必须对包含 10^6 个元素的数组进行排序。以下哪项是正确的？
- 插入排序总是需要 2.5 小时以上，而归并排序总是不到 1 秒。
- 插入排序总是需要 2.5 小时以上，而快速排序总是不到 1 秒
- 插入排序可能需要超过 2.5 小时，而归并排序总是需要不到 1 秒。
- 插入排序可能需要超过 2.5 小时，而快速排序总是需要不到 1 秒。
插入排序的最坏情况复杂度是多少？
合并排序和快速排序的最坏情况下的复杂度是多少？
有没有可能插入排序不到2.5小时？如果是，情况如何？
快速排序（或归并排序）的最佳复杂度是多少？ 插入排序的最佳情况复杂度是多少？
如果你回答了这些问题。你会很容易回答你的问题。
如果您不知道什么是最坏情况或最佳情况，请尝试找到这些问题的答案。
如果排序需要 10^12 步，如果您的 CPU 每秒执行 10^8 步，排序会持续多少秒（或几小时）？
对长度为 n 的数组进行快速排序、归并排序或插入排序需要多少步？
回答以上所有问题会让您离回答您的问题更近一步。 去做吧，我保证，你马上就能回答。
插入排序和快速排序的最坏情况复杂度为 O(n^2)。
合并排序的最坏情况复杂度为 O(n*log(n))
因此，对于插入排序和快速排序没有。步骤数 (10^6)^2 = 10^12
所以需要 10^12/10^8 = 10^4 or 10,000 seconds = 2.77hrs（因为 CPU 运算 10^8 steps/sec）
哪里，没有。合并排序的步骤是 (10^6*log(10^6)) = 6*10^6 个步骤，需要 (6*10^6/10^8) = 0.06secs 个，小于 1
但视情况而定，选项 1 或 3 可能是正确的，此处插入排序可能需要不到 2.5 小时，具体取决于问题，因为插入排序的平均情况复杂度是 (N-1)*N/4 计算 运行 时间，我们得到 0.69hrs 小于 2.5 小时，所以第三个陈述是正确的。