Какая временная сложность у простого алгоритма вычисления факториала (О большое)?

Question

[kaliboba]

Добрый день, я новичок и не могу понять, какая сложность у такого алгоритма, например реализованного так

def f(n):
    if n <= 1: return 1
    else:
        return n * f(n - 1)

заодно, какая сложность у такой реализации?

def f2(n):
    c = 1
    for i in range(1,n + 1):
        c *= i
    return c

Comments

[res2001]

O(n) в обоих случаях.

[Сергей delphinpro]

res2001, в первом случае количество операций линейно растёт от входного значения. Сложность линейная - O(n)
А во втором случае наверное стоит учесть внутреннюю реализацию функции range? Если там цикл, например, то O(n^2). Или не так?

[Alexandroppolus]

Сергей delphinpro, я полагаю, там всё-таки этот range вызывается однократно

[res2001]

Сергей delphinpro,

стоит учесть внутреннюю реализацию функции range?

Если в range используется yeld для возврата промежуточных значений, то в каждом вызове происходит только проверка условия окончания и возврат следующего значения. В этом случае сложность всего алгоритма остается O(n).
Если в range есть цикл, тогда он возвращает массив последовательных элементов [1; n+1] и дальше цикл итерируется по значениям из массива. В этом случае range вызывается один раз. Тогда сложность будет O(n+n) = O(2n) = O(n)

[Dmitrii]

Сергей delphinpro, конечно нужно, иначе какой смысл в такой оценке?
res2001 хорошо все расписал.

[Сергей delphinpro]

res2001, да, точно.

Answer 1

[Wataru]

Линейная сложность и там и там.