Найдите асимптотическое время работы следующих разделов кода. Ответом должны быть термины О и Тета.
Я думал о Theta (n ^ (1.5)), но я не уверен в этом. Что вы думаете ?
Найдите асимптотическое время работы следующих разделов кода
comment
Я голосую за то, чтобы закрыть этот вопрос как не по теме, потому что это не вопрос программирования, а скорее академический по своему характеру.
- person Pradeep Pati schedule 22.03.2016
comment
Если ответ помог, проголосуйте за него и примите ответ. Узнайте, как проголосовать за ответ --- ›meta.stackexchange.com/questions/173399/ и как принять ответ ---› meta.stackexchange.com/questions/5234/
- person Am_I_Helpful schedule 23.03.2016
Ответы (1)
Внутренний цикл выполняется n 1/2 (квадратный корень из n) раз для каждой итерации внешнего цикла.
Внешний цикл выполняется n раз.
Итак, чистая сложность запуска программы будет O (n * n 1/2) = O (n 3/2) = O (n 1.5 ).
Кроме того, поскольку более жесткая граница округлит его до временной сложности Big-Theta (n 1.5).
Итак, временная сложность кода = Θ (n ^ 1,5).
person
Am_I_Helpful
schedule
22.03.2016
