Обе ли эти факторные функции выполняются в O (n)?

Question

Рекурсивная функция, определенная так:

function factrec($x) {
    if($x <= 1) {
        return $x;
    } else {
        return $x * factrec($x - 1);
    }
}

И здесь итеративно:

function factiter($x) {
    $y = $x;
    while($y > 1) {
        $x *= ($y - 1);
        $y--;
    }
    return $x;
}

Я читал, что в рекурсивной функции тело - это O (1), а рекурсивные вызовы O (n-1) делают его O (n), но для итеративного тоже O (n)?

Answer 1

Да, обе версии запускаются за время O (n).Обоснование для итеративной версии в основном такое же, как и для рекурсивной версии: тело цикла выполняется за O (1) время и выполняется n раз.

Однако следует отметить, что итерационная версия выполняетсяв пространстве O (1), в то время как рекурсивная версия использует пространство стека O (n) (поскольку глубина рекурсии равна n).

Answer 2

да, это O (n). Попробуйте представить, сколько операций будет выполнять процессор, если у вас большое значение x. При больших значениях он не становится более сложным, и это всегда одна и та же операция линейным способом.