Сложность времени с «или» в ответном выражении

Question

У меня есть следующий код и я хочу вычислить сложность времени:

def solve(n):
    if n == 0 or n == 2:
        return True
    elif n == 1:
        return False
    else:
        return not solve(n-1) or not solve(n-2) or not solve(n-3)

Если бы у меня было что-то вроде этого:

return solve(n-1) + solve(n-2)

это было бы T (n) = 2T(n-1), по крайней мере, из моего понимания.

Но как мне поступить, если у меня есть "или" в выражении return?

return not solve(n-1) or not solve(n-2) or not solve(n-3)

Answer 1

Короткое замыкание является ключевой концепцией в этом случае:

return not solve(n-1) or not solve(n-2) or not solve(n-3)

Если результат первой функции ложен, то есть первый операнд логического ИЛИ равен true, тогда другойфункции не нужно оценивать (мы уже знаем общий результат).

Если результат первой функции истинен, то нам нужно оценить вторую функцию.Следуя тому же образу мышления, что и выше, если этот второй операнд оценивается как true, то мы закончили, и нам не нужно вызывать третью функцию.

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

---

И так как мы говорим о сложности времени, вам нужно думать с точки зрения наихудшего и наилучшего сценариев.

• Лучший вариант: один вызов функции.Сложность времени: T(n - 1).
• В худшем случае: три вызова функций.Сложность времени: T(n - 1) + T(n - 2) + T(n - 3).

Answer 2

Наихудшая временная сложность return not solve(n-1) or not solve(n-2) or not solve(n-3) равна T(n-1) + T(n-2) + T(n-3).

, а наилучшая - T(n-1).

Поскольку a or b не оценивает b, если aправда.

Answer 3

Вы должны рассмотреть наихудший случай.Давайте предположим, что not solve(n-1) и not solve(n-2) возвращают False.В этом случае всегда будет оцениваться solve(n-3).

С точки зрения сложности это то же самое, что и вычисление:

solve(n-1) + solve(n-2) + solve(n-3)

Answer 4

Обычно, говоря о сложности времени, мы думаем о худшем сценарии.Здесь, в самом худшем случае, вы будете вычислять solve для случая n-1, n-2 и n-3.

Следовательно, T (n) = T (n-1) +T (n-2) + T (n-3)