java - 程序的大 O 表示法(最坏情况)

Question

我有一个关于复杂性理论的问题。如果我有一个冒泡排序算法，并且我想找到它最坏情况下的运行时间 Big O，我们可以得出结论，它是 O(n^2)。现在，如果我有一个执行不同操作(如排序算法、搜索算法等)的程序，该怎么办？我如何知道该程序的最坏情况运行时间(Big O)一般是多少。

例如，程序中的不同算法及其各自的最坏情况运行时间 Big O 符号如何得出整个程序的最坏情况运行时间 (Big O) 的结论。就像当一个程序具有以下内容时:O(n^2)、O(1)、O(n)....这些符号中哪一个是代表整个程序的符号？

你如何找到这个程序最坏情况下的运行时间 Big 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) 渐近说话!这就是计算算法复杂度的方法。谈论程序“复杂性”没有多大意义。