Как узнать сложность кода при наличии цикла с неизвестными параметрами?

Question

[Nightmare A]

Мне вот интересно, как узнать сложность кода при наличии цикла с неизвестными параметрами?

Comments

[mayton2019]

При такой постановке вопроса - нельзя. Нужно брать исходник и смотреть на него и думать.

Ты, чтоб не играть в викторину - опубликуй свою лабораторную.

[Василий Банников]

В таком случае - никак.

[Nightmare A]

mayton2019, У меня, к сожалению, нет лабораторной.

[mayton2019]

Nightmare A, ну... тогда как в детском анекдоте. Нету ножек - и нет конфетки.

Или ты думал тебе сразу целую главу из Дональда Кнута здесь отквотируют?

Или как ты хотел вообще?

Answer 1

[Griboks]

Экспериментальным путем. Выполните несколько замеров, затем аппроксимируйте популярными формулами.

Comments

[Nightmare A]

Это в разы усложняет задачу.

[Griboks]

Nightmare A, профайлер - это основной метод анализа сложности кода. Вся теория - попытка предсказать работу профайлера. Но раз у вас код в виде чёрного ящика, вы не сможете его предсказать. Например, у вас могут быть динамические границы цикла и т.п.

Answer 2

[Сергей Горностаев]

Если речь про сложность алгоритма, то она зависит от структуры кода, а не объёмов обрабатываемых данных. А как отличить квадратичный алгоритм от логарифмического объясняют обычно в первых же главах любого учебника по алгоритмам.