电脑编程中快速排序的时间复杂度n log n 是n*log(n)还是什么

电脑编程中快速排序的时间复杂度n log n 是n*log(n)还是什么

问题中两者选择的答案是相同的，且是正确的，n log n 即等于n*log(n)，其中*代表乘，默认底数为2.
快速排序的复杂度为log以2为底，n^2的对数，也就是O（n^2），如排序10个数，最坏的情况就是O（10^2）=O(100)≈33

数据结构中logn一般表示2为底数，如果不是的话，才会明确标明。

复杂度的表示式里面只看幂级不看具体底数，log n跟log2n是一回事，感觉你有些概念不清的样子，时间复杂度的n就表示算法处理的数字个数，快速排序的时间复杂度就是n log n，快速排序10个数的时间复杂度也还是n log n，你可以说n=10，但是时间复杂度的表示式里面要求把具体的输入个数用n表示，因为这样才能反映出算法在输入个数增加的时候运行时间相应增加的程度，也就是“时间复杂度”这个概念本身想说明的问题。追问那比如n=10和n=20运算次数差了几倍呢？我指n log n的复杂度追答复杂度是抽象于运算次数的，它只是表明了一个算法实现所需要的运算次数随输入个数增加而增加的“速度”，是一个“度”而不是一个“数”。所以在比较时间复杂度的时候，我们比较的也同样只是“程度”而不是具体的运算“次数”，所以对于同一个算法（比如说你说的快速排序）来说，n=10跟n=100的复杂"程度"是一样的！因为复杂度本身就是把具体的输入个数抽象成n以后才能有表达式的。算法的时间复杂度是用来在算法之间互相比较的，比如说快速排序跟起泡排序两种不同的算法，快速排序的时间复杂度nlogn比起泡排序n^2更小，因为nlogn在n增大的时候增长的“速度”比n^2要快。

现在回答你的追问，在nlogn的复杂度下，n=10和n=20的运算次数都是未知的，所以不能比较差了几倍。

快速排序的平均复杂度是在n*log2(n)也就是nlog(n)，在信息学中nlog(n)的底数默认为2。至于说快速排序10个数的时间复杂度，是没办法计算的，这个还是和这10个数的初始顺序有关。只能说排序10个数的平均复杂度在10*log2(10)，如果这个10个序列差劲，复杂度也有可能是O(10^2)。（快速排序的最坏情况下的时间复杂度是O(n^2)）

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息