Блог

Главная - Вопросы по программированию - Время выполнения в lua

Время выполнения в lua

#algorithm #lua #time-complexity #runtime

#алгоритм #lua #время-сложность #время выполнения

Вопрос:

Итак, у меня есть следующий вопрос, который гласит:

 function f(n)
    local z=1
    for a=1,n do
        for b=1,z do
            for c=1,z do
                z=z 1
            end
        end
    end
    return z
end

и тогда это дает мне возможность:

Дайте наилучший ответ на следующий вопрос.

f(n) = …

 O(2^(2^n))

O(2^(2^(2^(2^(2^(2^n))))))

O(2^n)

O(2^(2^(2^n)))

O(2^(2^(2^(2^(2^n)))))

none of the others here

O(2^(2^(2^(2^n))))

Это для моего вычислительного класса lua, и я просто понятия не имею, как это сделать, я понимаю, что есть тройной цикл, и, скорее всего, вместо z них было бы все n , O(n^3) но в этом я не слишком уверен.

Я надеялся, что кто-нибудь сможет помочь / объяснить, как ответить на такой вопрос.

Спасибо.

Комментарии:

1. Когда z происходит удаление в этом утверждении for b=1,z do ... ? Может быть, это проще, чем мы думаем? Или попробуйте и выясните, что это очень высокого порядка…. `f (4)` еще не вернулся…

2. Правильный ответ: «ни один из других здесь». Время равно g(g(..g(1)..) где g применяется n-1 раз и g(z)=z*2^z . Он растет быстрее, чем любая цепочка питания фиксированной длины 2^2^2...

Ответ №1:

Во-первых, количество раз z=z 1 , которое выполняет оператор, равно значению z-1 в конце функции. Итак, если бы мы могли выразить f(n) аналитически, то сложность f функции была бы O(f(n)) . Давайте попробуем сделать это.

Во-вторых, давайте упростим функцию. Следующий цикл

             for c=1,z do
                z=z 1
            end

эквивалентно z=z*2 . Далее, следующий цикл

         for b=1,z do
            z=z*2
        end

эквивалентно z=z*(2^z) . Теперь мы можем переписать всю функцию равновалентно в виде следующего псевдокода:

 function f(n)
    local z=1
    for a=1,n do
        z=z*(2^z)
    end
    return z
end

Теперь мы можем выразить f(n) рекурсивно:

 f(n 1) = f(n) * 2^f(n) 
       = 2^(f(1)) * 2^(f(2)) * ... * 2^(f(n))
       = 2^(f(1)   f(2)   ... f(n))

Наконец, давайте приблизимся f(n) :

 f(n)   = 2^(f(1)   f(2)   ... f(n-1))
       ≥ 2^f(n-1)
       ≥ 2^(2^f(n-2))
       ≥ 2^^n

где a^^b = a^a^a^a^a...^a // a is there b times (это обозначение Кнута со стрелкой вверх для оператора тетрации).

Я предполагаю, что для любой константы c>0 следующее неравенство справедливо для достаточно большого n : 2^^n > c * 2^(2^(2^(2^(2^(2^n))))) , поэтому правильный ответ на вопрос «ни один из других здесь». Но я могу ошибаться.

Вы можете спросить в Computer Science StackExchange O(f(n)) , для чего f(n)=2^(f(1) f(2) ... f(n-1)) это нужно.