算法的复杂性，排序5%

Question

有人问我以下问题。

算法考虑n个元素，对n个元素排序5%，对剩余元素(95%)进行排序，对5%的剩馀元素进行排序，等等，直到最后剩下一个元素。算法的复杂度是多少?为什么？

Answer 1

大O时间复杂度的分而治之算法不受你把事情分成的分数的影响。这是因为不同基础的日志只相差一个常数因子。所以，在你的情况下，大O时间的复杂性是一样的，就像你把50%的时间分开一样。

因此，您应该得到通常的nLogn排序。