Средняя сложность случая функции

Question

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

def d(a):    
    for i in range(len(a)):
        if a[i] == 0 or a[i] == 1:
            for j in range(i+1, len(a)):
                if not (a[j] == 0 or a[j] == 1):
                    swap(a, i, j)
                    break

Что выПодумайте, как подойти к этой проблеме математически?

Answer 1

Опуская все детали, мы получаем два вложенных цикла, указывающих квадратичный алгоритм.Принимая во внимание if, такой небольшой процент чисел фактически выполняет внутренний цикл, что средний регистр эффективно линейный.

Answer 2

for i in range(len(a)):

Результатом будет длина a, умноженная на среднее время для любого индекса в range(len(a)) (давайте пока проигнорируем break).

if a[i] == 0 or a[i] == 1:

Два доступа к значениям a, поэтому давайте добавим 2 * [time to retrieve a[i]]. Вероятность того, что значение a (элемент бесконечного множества, ℕ) является элементом любого конечного множества (такого как {0,1}), бесконечно близка к нулю. Поскольку дальнейший код внутри занимает конечное время, мы можем спокойно его игнорировать.

Средняя сложность случая: 2 len(a) [time to retrieve a[i]] ∈ Θ(len(a)) ⊂ O(len(a)).