Big-O & Big-Theta: является временной сложностью цикла O (1)?

Question

У меня проблемы с пониманием того, что означает Big-O и Big-Theta. Может кто-нибудь объяснить, что это означает иллюстративно?

Учитывая, что n является константой, является ли цикл цикла O (1) для наихудшего случая?

Кроме того, это наихудшее время работы алгоритма ниже O (n^2), так как insertionSort имеет сложность O (n^2)? Если нет, какова временная сложность приведенного ниже алгоритма для наихудшего случая?

void fnA(int[] array) 
{ 
    ArrayList a2 = new ArrayList<Integer>(array.length); 

    for (int i=0; i<n; i++) { 
     a2.add(array[i]); 
     insertionSort(a2); 
    } 
} 

Answer 1

Вы можете думать о Big-O как о верхней границе. Если у вас есть цикл for. Скажите

for i:= 1 to 10 print("hello"); 

то это сложность O (1). O (1) не означает, что он завершен в 1 инструкции. Это просто означает, что он не меняется в зависимости от времени работы с учетом размера ввода (который равен n). Аналогично, O (n) означает, что его время работы прямо пропорционально размеру ввода.

Для вашего примера вы можете сделать это простым, подумав так: у вас есть внешняя петля со сложностью O (n). Затем внутри тела цикла вы вызываете add (это O (1)) и insertionSort, который является O (n^2). Тогда полная сложность равна O (n) * (max (O (1), O (n^2)) = O (n^3).

На самом деле это всего лишь быстрый способ оценки сложности. более точный метод, вы должны сделать некоторую математику, например, когда длина a2 равна 1, 2, 3. ..., n, сколько инструкций необходимо выполнить во вставке, а затем суммируйте их. некоторая формула с самым значительным членом равна n^3.