Алгоритм BruteForceMedian имеет квадратичную эффективность. (Зачем?)

Question

Этот алгоритм имеет квадратичную эффективность. (Зачем?)

Answer 1

Чтобы проанализировать сложность, вам просто нужно посчитать количество операций.

Здесь есть два вложенных цикла:

for i in 0 to n – 1 do
    for j in 0 to n – 1 do
        operation() // Do something
    done
done

С i = 0, operation будет выполняться для всех j в [0,n-1], то есть n раз. Затем увеличивайте i и повторяйте, пока i > n-1. Это operation побежал n*n раз в худшем случае.

Таким образом, в конце концов, это коды n^2 операции, поэтому он имеет квадратичную эффективность.

Answer 2

Это вопрос с подвохом, он может быть одновременно n^2 и 2^n в зависимости от того, выполняется ли оператор if в строке j.