Блог

Какова временная сложность и тильда для цикла ниже?

 for (int i = N/2; i < N; i  ) {
    for (int j = i; j < N; j  ) {
        doSomething(i, j);
    }
}
  

Я думаю, что это выполняется N/2 (N/2 1) (N/2 2) ... (N-1) раз, но как мне получить временную сложность и тильду?

Например, если N = 100 , цикл будет выполняться 50 51 52 53 ... 99 несколько раз.

Я предполагаю, что doSomething(i, j); не повторяет все элементы между i и j; если это так, сложность этого алгоритма равна O (N ^ 2).

Внешний цикл for (int i = N /2; i < N; i ) { будет выполняться O (N) раз, потому что N / 2 на самом деле является постоянным значением.

Внутренний цикл в худшем случае также будет выполняться N раз (или N — i раз), это также объединится с предыдущим O (N).

Следовательно, общая временная сложность будет равна O (N ^ 2) в худшем случае.

Выполняется внутренний цикл:

N / 2-1 раз для i = N / 2,

N / 2-2 раза для i = N / 2 1

….

1 раз для i = N-2

следовательно, общее время для внутреннего цикла равно :

(N /2-1) (N / 2-2) …. (N / 2-k) где k = N / 2 — 1

= N /2*k — (1 2 … k)

= N /2 * (N /2-1) — (N /2-1) (N / 2)/2

= N /2(N/2 — 1 — N /4 1/2)

= N / 2 (N / 4 — 1/2)

= N ^ 2/8 — N / 4

Следовательно, порядок роста кода имеет N^2

Если вы рассматриваете тильдовую нотацию, которая определяется как :

« ∼g(n) для представления любой величины, которая при делении на f(n) приближается к 1 по мере роста n» отсюда вы можете видеть, что ~g(n) = ~N^2/8 , потому что по мере N роста (N^2/8)/(N^2/8-N/4) приближается к 1.