Сегодня все утро пыталась довести до ума пост о вычислительной сложности. Но все же это сложновато объяснить без самого кода. Обычно вычислительную сложность объясняют сразу на коде, подсчетом элементарных операций, потом устремляя входные данные к бесконечности (привет пределам!) и...вот как это все объяснить? Для меня тема вычислительной сложности всегда была мутная, я где-то на подсознательном уровне примерно определяю асимптотику и всю жизнь пользовалась только обозначением О-большое. А стала тут копаться... Тема то очень интересная! Очень важная и базовая. Ну как теория алгоритмов без вычислительной сложности? Без временной и емкостной сложностей?

А тут стала писать пост, думая о том, ну чего тут сложного? Есть входные данные, есть какая-то зависимость, есть предельная граница худшего варианта, что тут объяснять? Все предельно просто, особенно если буду рассказывать в контексте той задачи, которую разобрали в прошлый раз. А тут вдруг приплелись комбинаторика, математический анализ и теория вероятностей. И вот ту понимаешь, что во-первых плаваешь в теме, а во-вторых вот тебе и образование - все университетские предметы все это время были связаны. Не, это и так понятно было, но я никогда не сталкивалась с этим вплотную.

А еще я думала, что это будет проходным материалом, а потом начнется самая жара, когда затронем P и NP - классы. Эх, все же логично начинать изучать алгоритмистику с сортировок, поиска и представления данных. Даже на тех же сортировках вычислительную сложность объяснить намного легче, чем на NP-трудной задаче =___=