我认为我理解的内容。
在最坏的情况下，快速排序算法会为每个递归调用选择列表/数组中最大或最小的键进行排序(如果是递归实现)。我知道n的大小将决定递归调用的次数和比较的次数(每递归一步就会减少1)。所以我们总共有 n+(n-1)+(n-2)+...+2+1 次原始比较。
我不明白。
我不太明白的是这是怎么O(n^2)？就像我知道它至少是 O(n^2) 作为 n+(n-1)+(n-2)+...+2+1 < n^2 但我怎么知道它不是说 O (n*logn)？我是否必须证明该结果才能安全地确认它是 O(n^2) 还是以我看不到的方式立即显而易见？我想一般来说我怎么知道我已经找到了代表大 O 时间复杂度的最低函数。
最佳答案
n+(n-1)+(n-2)+...+1 = n(n+1)/2(可以通过数学归纳法证明)，显然是O(n^2)。
https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF
关于big-o - 最坏情况快速排序的大O时间复杂度？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37771460/