時間複雜度（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）

回答

相關問題