我坚持要为即将到来的测试进行修订。
问题是:
An implementation of insertion sort spent 1 second to sort a list of 10^6 records. How many seconds it will spend to sort 10^7 records?
通过使用
T(X)/T(1) = 10^7/10^6
我以为答案是 10 秒，但实际答案是 100 秒。
有人可以帮帮我吗？
最佳答案
如果插入排序是在线性(即O(n))时间内运行的操作，那么您的答案应该是正确的。但事实并非如此。
插入排序的平均复杂度为 O(n^2)(即它是二次的)。粗略地说，这意味着平均需要 4 倍的时间来排序 2 倍的记录；排序 3 倍的 9 倍；排序 4 倍的 16 倍；等等。
题目问你排序10倍多的记录需要多长时间； 10 的平方乘以 1 秒是多少？
关于algorithm - 使用插入排序对 10^7 条记录进行排序所花费的时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26825204/