我目前正在做一些考试题目,并且此时陷入困境.我得知Quicksort算法的时间复杂度为O(nlog(n)).对于特定输入大小,对列表进行排序的时间为4分钟.问题继续问在同一系统上对两倍大小的列表进行排序需要多长时间.
我已经排除了时间不是8分钟(输入大小的两倍=持续时间的两倍,非常非常错误的推理).
我做过一些工作:
工作A.
4 = nlog(n)4 = log(n^n)16 = n^n工作B.
X = 2nlog(2n) >> 2n 因为输入加倍X = 2n(1 + log(n))X = 2n + 2nlog(n) >> nlog(n)是4几分钟X = 2n + 2(4) = 2n + 8