时间复杂度（Java，快速排序）

Question

我有一个关于计算时间复杂度（大 O 表示法）的非常普遍的问题。当人们说 QuickSort 的最差时间复杂度是 O(n^2)（每次都选择数组的第一个元素作为基准，并且数组是反向排序的）时，他们考虑了哪个操作来得到 O(n ^2)?人们会计算 if/else 语句所做的比较吗？或者他们只计算它进行的掉期总数？一般来说，你怎么知道要计算哪个"steps"来计算大O符号。

我知道这是一个非常基本的问题，但是我已经阅读了几乎所有关于 google 的文章，但仍然没有弄明白

Answer 1

快速排序的最坏情况
快速排序的最坏情况是数组被逆向排序，正常排序并且所有元素都相等。

了解大佬
说到这里，我们先来了解一下Big-Oh of something是什么意思吧。

当我们只有渐近上界时，我们使用 O-notation。对于给定的函数 g(n)，我们用 O(g(n)) 表示函数集， O(g(n)) = { f(n) : 存在正 c 和 n_o,
这样 0<= f(n) <= cg(n) 对于所有 n >= n_o}

我们如何计算Big-Oh？
Big-Oh 基本上意味着程序的复杂性如何随着输入大小而增加。

代码如下：

import java.util.*;
class QuickSort
{
    static int partition(int A[],int p,int r)
    {
        int x = A[r];
        int i=p-1;
        for(int j=p;j<=r-1;j++)
        {
            if(A[j]<=x)
            {
                i++;
                int t = A[i];
                A[i] = A[j];
                A[j] = t;
            }
        }

        int temp = A[i+1];
        A[i+1] = A[r];
        A[r] = temp;
        return i+1;
    }
    static void quickSort(int A[],int p,int r)
    {
        if(p<r)
        {
            int q = partition(A,p,r);
            quickSort(A,p,q-1);
            quickSort(A,q+1,r);
        }
    }
    public static void main(String[] args) {
        int A[] = {5,9,2,7,6,3,8,4,1,0};
        quickSort(A,0,9);
        Arrays.stream(A).forEach(System.out::println);
    }
}

考虑以下陈述：

区块 1：

int x = A[r];
int i=p-1;

第 2 块：

if(A[j]<=x)
{
     i++;
     int t = A[i];
     A[i] = A[j];
     A[j] = t;
}

区块 3：

int temp = A[i+1];
A[i+1] = A[r];
A[r] = temp;
return i+1;

区块 4：

if(p<r)
{
    int q = partition(A,p,r);
    quickSort(A,p,q-1);
    quickSort(A,q+1,r);
}

假设每条语句花费固定时间c。让我们计算一下每个块计算了多少次。

第一个块被执行 2c 次。第二个块执行 5c 次。口渴块被执行4c次。

我们将其写为 O(1)，这意味着即使输入大小不同，语句执行的次数也相同。所有 2c、5c 和 4c 都是 O(1)。

但是，当我们在第二个块上添加循环时

for(int j=p;j<=r-1;j++)
{
    if(A[j]<=x)
    {
        i++;
        int t = A[i];
        A[i] = A[j];
        A[j] = t;
    }
 }

它运行s n次（假设r-p等于n，输入的大小）即nO(1)次即O(n ).但这并不是每次都运行 n 次。因此，我们有平均情况 O(log n)，即至少遍历 log(n) 个元素。

我们现在确定分区运行s O(n) 或 O(log n)。最后一个块，即 quickSort 方法，在 O(n) 中定义为运行s。我们可以将其视为一个包含运行s n 次的封闭 for 循环。因此整个复杂度是 O(n²) 或 O(nlog n).

Answer 2

主要是看可以增长的大小(n)，所以对于数组快排就是数组的大小。您需要访问数组的每个元素多少次？如果你只需要访问每个元素一次那么它是一个 O(n) 等等..

随着n的增长而增长的临时变量/局部变量将被计算在内。其他在n增长时增长不明显的变量可以算作常量：O(n) + c = O(n)

Answer 3

只是补充一下其他人所说的，我同意那些说你计算一切的人，但如果我没记错的话我在大学类的算法，与比较相比，交换开销通常是最小的次，在某些情况下为 0（如果相关列表已经排序）。

例如。线性搜索的公式是

T= K * N / 2.

其中T是总时间； K 是定义总计算时间的常数； N 是列表中的元素数。

平均而言，比较次数为N/2。

但我们可以将其重写为以下内容：

T = (K/2) * N

或重新定义K，

T = K * N.

这就明确了时间与N的大小成正比，这才是我们真正关心的。随着 N 显着增加，它成为唯一真正重要的东西。

另一方面，二进制搜索以对数方式增长 (O log(N))。

时间复杂度（Java，快速排序）

Time complexity(Java, Quicksort)

java

big-o

quicksort