最坏情况快速排序的大O时间复杂度？
Big O time complexity of worst case quick sort?
我觉得我明白了。
在最坏的情况下，快速排序算法会选择 list/array 中最大或最小的键，以便为每个递归调用（如果是递归实现）进行排序。我知道 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*登录）？我是否必须证明该结果才能安全地确认它是 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
我觉得我明白了。
在最坏的情况下，快速排序算法会选择 list/array 中最大或最小的键，以便为每个递归调用（如果是递归实现）进行排序。我知道 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*登录）？我是否必须证明该结果才能安全地确认它是 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