Какова временная сложность \ big (O) этой конкретной функции?

Question

Какова временная сложность этой функции (f1)?

, так как я вижу, что первый цикл (i = 0) -> (n / 4 раза), второй (i = 3)-> (n / 4 - 3 раза) .... и т. д., результат: (n / 3) * (n / 4 + (n-3) / 4 + (n-6) / 4 + (n-9) / 4 ....

И я остановлюсь здесь, как продолжить?

int f1(int n){
  int s=0;
  for(int i=0; i<n; i+=3)
    for (int j=n; j>i; j-=4)
      s+=j+i;
  return s;
}

Answer 1

Теоретически это "O (n * n)", но ...

Что если компилятору захочется оптимизировать его так:

int f1(int n){
  int s=0;
  for(int i=0; i<n; i+=3)
    s += table[i];
  return s;
}

Или даже так:

int f1(int n){
  if(n <= 0) return 0;
  return table[n];
}

Тогда это также может быть "O (n)" или "O (1)".

Обратите внимание, что на первый взгляд эти виды оптимизаций кажутся непрактичными (из-за памяти наихудшего случая)расходы);но с достаточно продвинутым компилятором (например, используя «оптимизацию всей программы», чтобы проверить всех вызывающих и определить, что n всегда находится в определенном диапазоне), это немыслимо.Аналогичным образом, невозможно, чтобы все вызывающие абоненты использовали константу (например, когда достаточно продвинутый компилятор может заменить такие вещи, как x = f1(123); на x = constant_calculated_at_compile_time).

Другими словами;на практике временная сложность исходной функции зависит от того, как она используется и насколько хорош / плох компилятор.

Answer 2

Ключевое наблюдение: Внутренний цикл выполняется (n-i)/4 раз на шаге i, следовательно i/4 на шаге n-i.

Теперь суммируйте все эти величины для i = 3k, 3(k-1), 3(k-2), ..., 9, 6, 3, 0, где 3k является наибольшим кратным 3 до n (т. е. 3k <= n < 3(k+1)):

3k/4 + 3(k-1)/4 + ... + 6/4 + 3/4 + 0/4 = 3/4(k + (k-1) + ... + 2 + 1)
                                        = 3/4(k(k+1))/2
                                        = O(k^2)
                                        = O(n^2)

, поскольку k <= n/3 <= k+1 и, следовательно, k^2 <= n^2/9 <= (k+1)^2 <= 4k^2

Answer 3

Важной особенностью нотации Big (O) является то, что она исключает «константы».Цель состоит в том, чтобы определить тренд по мере того, как размер входных данных растет без учета конкретных чисел.

Думайте об этом как об определении кривой на графике, где вы не знаете диапазоны чисел xи оси y.

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

. Не имеет значения, рассчитали ли вы что-либо из следующего:

1/4 * n^2
0.0000001 * n^2
(1/4 * n)^2
(0.0000001 * n)^2
1000000 + n^2
n^2 + 10000000 * n

В Big O,все они эквивалентны O(n^2).Дело в том, что как только n становится большим достаточно (что бы это ни было), все члены более низкого порядка и постоянные факторы становятся неактуальными в «большой картине».

( Стоит подчеркнуть, что именно поэтому для небольших входов следует опасаться слишком сильной зависимости от Big O. Именно тогда постоянные накладные расходы могут по-прежнему оказывать большое влияние. )