Анализ псевдокода

Question

Я просматриваю прошлые документы, которые мой университет выпускает, однако по какой-то причудливой причине они не выпускают для них образцовые решения.

Мне просто интересно, правильно ли я выполнил анализ сложности для этого фрагмента псевдокода.

Вот псевдо-код (извините за ссылку Imgur, PDFs испортили формат синтаксиса): http://i.stack.imgur.com/vGst2.png

Когда я сделал анализ я получил O (N^4). Это главным образом квадрат и кубирование ввода в петлях, которые меня путают, мы не рассматривали это в классе, и я не могу найти на нем никаких онлайн-ресурсов.

Answer 1

Предполагая, что «дисплей (I, J)» выполняется в постоянном времени (или одна операция), и что не считать каких-либо затрат для приращения переменных, то общая стоимость:

Н * ((N^3 - 4) + (N^2 + 1)) = N^4 + N^3 - 3N

Вы правы, что это O (N^4). Это связано с тем, что (при достаточно большом N) N^4 + N^3 - 3N < = 2N^4.