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

Question

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

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

Кроме того, является ли время выполнения алгоритма в наихудшем случае ниже O(n^2), поскольку метод inserttionSort имеет сложность 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 i:= 1 to 10 print("hello");

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

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

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