程序的大O表示法（最差情況）

Question

我有一個關於複雜性理論的問題。如果我有一個Bubble排序算法，並且我想查找其最壞情況運行時間Big O，我們可以得出結論，它是O（n^2）。現在，如果我有一個執行不同操作（如排序算法，搜索算法等）的程序，我怎麼知道這個程序的最壞情況運行時間（大O）。

例如，程序中的不同算法與其各自的最壞情況運行時間Big O符號如何得出整個程序的最壞情況運行時間（大O）的結論。就像一個程序有以下內容：O（n^2），O（1），O（n）....這些符號中的哪一個是代表整個程序的符號？

你會如何找到最糟糕的運行時間這個程序的大O？

import java.util.*; 
public class Prog1 { 
    public static void main(String[] args) { 

    int first = 0; 
    int last; 
    int middle; 
    int search; 
    int[] array; 

    Scanner input = new Scanner(System.in); 
    System.out.println("Number of elements"); 
    int n = input.nextInt(); 

    array = new int[n]; 

    System.out.println("Enter " + n + " value "); 
    for (int x = 0; x < n; x++) { 
     array[x] = input.nextInt(); 
    } 

    System.out.println("Value to search"); 
    search = input.nextInt(); 

    last = n - 1; 
    middle = (first + last)/2; 

    while (first <= last) { 
     if (array[middle] < search) 
      first = middle + 1; 
     else if (array[middle] == search) { 
      System.out.println(" Number " + search + " is in the array"); 
      break; 
     } else 
      last = middle - 1; 

     middle = (first + last)/2; 
    } 
    if (first > last) 
     System.out.println(" Number " + search + " is not in the list."); 
} 
} 

Answer 1

最高的一個。 O（n^2）+ O（n）+ O（1）= O（n^2）漸近地說話！ 這就是你將如何計算算法的複雜性。談論節目「複雜性」沒有多大意義。