У меня вопрос по теории сложности. Если у меня есть алгоритм сортировки пузырьком, и я хочу найти его худшее время работы, большое O, мы можем сделать вывод, что это O (n ^ 2). Теперь, что насчет того, если у меня есть программа, которая выполняет различные операции, такие как алгоритм сортировки, алгоритм поиска и т. д. Как мне узнать, какое время выполнения этой программы в наихудшем случае (большой O) в целом.
Например, как наличие разных алгоритмов в программе с соответствующими нотациями Big O для наихудшего случая приводит к заключению о времени выполнения в наихудшем случае (Big O) всей программы. Например, когда программа имеет следующее: O(n^2), O(1), O(n).... Какая из этих нотаций представляет всю программу?
Как бы вы нашли наихудшее время выполнения этой программы?
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.");
}
}
n
? - person Oliver Charlesworth   schedule 29.09.2014