Помогите найти сложность алгоритма

Draeden · Сообщение **Draeden** » 28 июн 2009, 19:08

Из такого определения получается, что все задачи из одной категории решаются за одно количество операций.

gaal · Сообщение **gaal** » 28 июн 2009, 19:17

Draeden писал(а):Source of the post
Из такого определения получается, что все задачи из одной категории решаются за одно количество операций.

Извини, братан, и пойми правильно.
Ha изучение теории алгоритмов отводится целый семестр, на эту тему написано много книг.

Простого понимания основ вычислительной техники недостаточно, чтобы решить эту не совсем тривиальную задачу o трудоемкости программы. A именно это ты сейчас пытаешься сделать.

Так что спасибо и всего наилучшего.

Draeden · Сообщение **Draeden** » 29 июн 2009, 09:11

Сложность алгоритма видна на глаз. Я лишь хочу сказать, что хорошее определение сложности сразу даст ответ на вопрос в сабже.

Pavlovsky · Сообщение **Pavlovsky** » 29 июн 2009, 10:47

Немогу понять сути обсуждения.
При работе алгоритма выполняется 2n операций умножения и 5n опреций сложения. Плюс минус небольшие константы. Причем никакой асимптотики и наихудшего варианта, цифры верны для любого n.
Вывод естественен: время работы алгоритма линейное O(n).

yourdomain.com