Big-O маленькой петли

Question

У меня проблема с упражнением, которое я должен выполнить для Uni, это следующее:

Эта функция получает строку s и возвращает true, если s содержит две первые буквы данного строка sub (в нижнем регистре и в любом порядке). В противном случае он возвращает false.

Некоторые примеры: допустим, что sub = "Euler", тогда он проверяет 'e' и 'u'. Таким образом, s = «да пребудет с тобой сила», затем верните истину. s = "комната 31", затем верните false. s = "un93ike1s", затем верните true.

Выберите самую сложную (наихудший случай) сложность из следующих строк.

function contains_two_letters(s, sub, n)

/* create a vector with two entries, both set to false */ 
found = [ false, false ]               (1)

for (i = 0; i < n; i++)                (2)
    for (k = 0; k < 2; k++)            (3)
        if s[i] == sub[k]:             (4)
            found[k] = true
            break
return (found[0] and found[1])

Я знаю / предполагаю, что: (1) - это O (1),

(2) - это O (n) и

(4) равно O (1),

, но как насчет (3) ?

Проблема : мы никогда не видели пример того, что al oop запускается только дважды, поэтому я предполагаю, что это O (2), но это не вариант в раскрывающемся списке.

Доступны следующие опции: O (n), O (1), O (n ^ 2) и O (log (n))

Любая помощь будет оценена.

Answer 1

Помните, что Big-O напрямую не касается производительности или количества операций в алгоритме: все дело в отслеживании того, как количество операций изменяется по мере увеличения размера проблемы.

Если есть al oop, который не случается больше раз по мере того, как n увеличивается к бесконечности, то это l oop является постоянным временем и упрощается до O(1). Неважно, насколько это дорого или сколько раз это происходит. Он может повторяться миллион раз, но если увеличение n не повлияет на него, оно все равно O(1).

Строка 3 в вашей задаче, следовательно, O(1), а строка 2 (и общая функция) - O(n), потому что внешний l oop - единственный, который встречается чаще, чем n увеличивается.