Помогите понять причину.
Есть большой кусок кода, разобраться полностью в котором достаточно сложно.
Код на вход получает некую последовательность из N элементов и что-то с ними делает.
По результатам эксперимента получается, что производительность экспоненциально зависит от N
Можно ли назвать какие-то общие моменты из за которых возникает экспонента?

Если вопрос идиотский, то сорри.

Так можно ли сказать откуда может появлятся экспонента?

Здравствуйте, valmond, Вы писали:

V>Так можно ли сказать откуда может появлятся экспонента?

Может, профайлером его?

L>Может, профайлером его?
Делал, ясности не внесло особо.
Дело в том, что там один огромный метод и профайлер сильно не помогает понять, что именно там внутри метода происходит.

Здравствуйте, valmond, Вы писали:

L>>Может, профайлером его?
V>Делал, ясности не внесло особо.
V>Дело в том, что там один огромный метод и профайлер сильно не помогает понять, что именно там внутри метода происходит.

Ну, профайлер понятие широкое
Можно попробовать понавставлять своих обьектов, которые прописывают в глобальный map сколько раз в них входили и сколько времени провели.

V>Можно ли назвать какие-то общие моменты из за которых возникает экспонента?

Самое простое, что приходит в голову, это перебор с возвратом. Обычно реализуется рекурсивным алгоритмов. Упрощенно, если на каждом шаге число вариантов, которые надо перебрать, K, а всего надо выбрать N компонентов, то число действий порядка K^N.

Здравствуйте, valmond, Вы писали:

V>Помогите понять причину.
V>Есть большой кусок кода, разобраться полностью в котором достаточно сложно.
V>Код на вход получает некую последовательность из N элементов и что-то с ними делает.
V>По результатам эксперимента получается, что производительность экспоненциально зависит от N
V>Можно ли назвать какие-то общие моменты из за которых возникает экспонента?

V>Если вопрос идиотский, то сорри.
Добрый вечер. Смотрите. Что такое увеличение сложности алгоритма? Это приведения алгоритма к NP полноте. Следовательно, в вашем случае можно предположить, что в Вашей программе присутствует алгоритм полного перебора или его аналог.
Вероятно так.

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, valmond, Вы писали:

V>>Помогите понять причину.
V>>Есть большой кусок кода, разобраться полностью в котором достаточно сложно.
V>>Код на вход получает некую последовательность из N элементов и что-то с ними делает.
V>>По результатам эксперимента получается, что производительность экспоненциально зависит от N
V>>Можно ли назвать какие-то общие моменты из за которых возникает экспонента?

V>>Если вопрос идиотский, то сорри.
А>Добрый вечер. Смотрите. Что такое увеличение сложности алгоритма? Это приведения алгоритма к NP полноте. Следовательно, в вашем случае можно предположить, что в Вашей программе присутствует алгоритм полного перебора или его аналог.
А>Вероятно так.

А что такое "приведение алгоритма к NP-полноте"? Только сначала сюда: http://en.wikipedia.org/wiki/NP-complete