时间复杂度（Java，Quicksort）

关于计算时间复杂度（大O表示法），我有一个非常普遍的问题。当人们说QuickSort的最坏时间复杂度是O（n^2）（每次选择数组的第一个元素作为枢轴，并且数组是反向排序的）时，他们要考虑哪个操作来获得O（n^2）？人们是否会计数if/else语句所做的比较？还是他们只计算它所做交换的总次数？一般来说，您如何知道要计算大O符号的计数“步骤”。时间复杂度（Java，Quicksort）

我知道这是一个非常基本的问题，但我读过几乎所有谷歌的文章，但还没有想通了

来源

2016-11-13 Hello

你们都算两者。 –

所以一般来说，你算过所有的操作？就像for循环增量一样，if/else和everything？只是好奇，因为对于线性搜索，我被教导我应该只计算比较的数量，因为这是我们感兴趣的主要操作。 – Hello

如前所述，您可以统计两个（所有操作）。然后那些复杂性（操作计数）将彼此相加，并且选择它们中的最大值。 :) – YoungHobbit

快速最差的情况下，排序
最差的快速排序的情况下，当数组被反向排序时，正常排序并且所有元素都相等。

了解大哦
说了这么多，让我们先了解什么东西大哦手段。

当我们只有渐近上界时，我们使用O-notation。对于一个给定的函数g（n），我们用O（g（n））表示函数的集合O（g（n））= {f（n）：存在正的c和n _,,
使得0 < = F（N）= < CG（N）对于所有n> = N _Ø}

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

假设每个语句取为恒定时间Ç。我们来计算每个块的计算次数。

第一个块被执行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倍（假定RP等于n，则输入的大小），即，否（1）倍即上）。但是这不会每次运行n次。因此，我们有平均情况O（log n），即至少log（n）个元素被遍历。

我们现在确定分区运行O（n）或O（log n）。最后一个块是quickSort方法，定义在O（n）中运行。我们可以将它想象成一个循环，它运行于n次。因此整个复杂度为O（n ）或O（nlog n）。

来源

2016-11-13 02:50:27

你的答案可能已被切断 – Hello

兄弟，我想你留下你的回答不完整。 – Thrasher

这是一个意外。我现在正在完成它。 –

它主要依赖于可以增长的大小（n），因此对于快速排列它是数组的大小。您需要多少次访问阵列的每个元素？如果你只需要访问每个元素一次，那么它是一个O（n）等等。

随着n的增长而增长的临时变量/局部变量将被计数。当n增长时，没有显着增长的其他变量可以算作常数：O（n）+ c = O（n）

来源

2016-11-13 03:27:01

只是为了增加别人的评价，我同意那些说你数数，但如果我从大学的算法类中正确记得，与比较时间相比，交换开销通常很小，在某些情况下，它是0（如果问题列表已经排序）。

例如。为线性搜索公式是

T = K * N/2

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

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

但我们可以重写此为以下：

T =（K/2）* N

或重新定义K，

T = K * N.

这使得很明显，时间与N的大小成正比，这正是我们真正关心的。随着N的显着增加，它成为唯一真正重要的事情。

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

来源

2016-11-13 03:43:57 TDWebDev

时间复杂度（Java，Quicksort）

回答

相关问题