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

Question

我有一个关于计算时间复杂度的非常普遍的问题（大O符号）。当人们说QuickSort最差的时间复杂度是O（n^2）（每次都选择数组的第一个元素作为轴心，并且数组是反向排序的）时，他们考虑了哪个操作来获得O（n^2）？人们会计算if/else语句所做的比较吗？或者他们只计算其进行的互换的总数？一般来说，你如何知道计算大O符号需要计算哪些“步骤”。

我知道这是一个非常基本的问题，但我已经阅读了谷歌上几乎所有的文章，但仍然没有弄清楚

Answer 1

为了补充其他人所说的话，我同意那些说你什么都算数的人，但如果我在大学里正确地回忆起我的算法课，与比较时间相比，交换开销通常是最小的，在某些情况下是0（如果所讨论的列表已经排序）。

例如。线性搜索的公式为

T= K * N / 2。

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

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

但是我们可以将它改写为:

T=（K/2）*N

或重新定义K，

T = K * N。

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

另一方面，二叉搜索以对数方式增长（O log（N））。

Answer 2

它主要计算在可以增长的大小（n）上，因此对于快速排序数组，它是数组的大小。您需要访问数组的每个元素多少次？如果您只需要访问每个元素一次，那么它是O（n）以此类推…

随着n的增长而增长的温度变量/局部变量将被计算在内。当n增长时没有显著增长的其他变量可以算作常量：O（n）c=O（n

Answer 3

快速排序的最
坏情况 快速排序的最坏情况是数组反向排序、正常排序且所有元素相等。

了解大噢
说完了，让我们先了解一下什么是大噢。

当我们只有渐近上界时，我们使用O-表示法。对于给定的函数g（n），我们用O（g（n））表示函数集，O（g（n)) = { f（n）：存在正c和n_o，
使得0

我们如何计算大-哦？< br> 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);
    }
}

考虑以下声明：

第一部分:

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;
    }
 }

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

我们现在确定分区运行O（n）或O（logn）。最后一个块是quickSort方法，定义为在O（n）中运行。我们可以将其视为一个运行n次的封闭for循环。因此，整个复杂度要么是O（n＜sup＞2