Какая математика нужна для книги: Алгоритмы. Построение и анализ
Читаю книгу "Алгоритмы. Построение и анализ" Кормена. Честно говоря, не понятно вообще ничего - все эти множества, функции g(n) и прочее. По статьям и видео я понимаю, что такое О-большое, как измеряется время алгоритма, наихудшие случаи и так далее, но совершенно не понимаю смысла математики в его книге. Например, сортировка вставками - там приведен код, я его понимаю, могу повторить, понимаю скорость работы данной сортировки, но все эти инварианты и множества - не могу понять, зачем они нужны и зачем так усложнять книгу. Знаю математику на уровне универа, она мне нравится, я не против нее, но в этой книге, она, как мне кажется, бесполезная, только если вы не работаете в сфере Computer Science (я пишу на змее и на си, область работы - backend). В чем вопрос. Действительно ли нужно разбираться в этой книге досконально вместе с математикой? Какой уровень математики нужен для этой книги? Потому что, скорее всего, в следующих главах будет хуже. Может быть, можно просто читать эту книгу без вникания во всю эту математику, потому что если опустить все эти "функция принадлежит множеству" книга, сама по себе, неплохая, если судить по тому, что я успел прочитать.
Ответы (1 шт):
Кормен - является базой для того, чтобы разобраться в алгоритмах и структурах данных. Если вам интересно почему там так много математики, все просто - она нужна для доказательства. Простой пример: вот у вас есть пузырьковая сортировка, понятно почему она работает за O(n^2) перебираются все пары элементов. Есть уже сортировка слиянием и тут встает вопрос почему там появляется логарифмический множитель, математика это доказывает, это все можно было понять и без нее, но тут появляется алгоритм Манакера (поиск самого длинного палиндрома в строке), он работает за O(n), но без математики доказать что работает он за n сложно, потому что на вид он работает за n^2. Если вы просто читаете о алгоритмах воспринимая их как данность, ну есть у нас сортировка подсчетом, работает она за n, ладно, то можете спокойно их пропускать, но если вам интересно знать, почему именно такая сложность алгоритма, или почему он будет оптимальный (например, алгоритм Краскала) то вам нужно их читать. Из советов, можете почитать что-нибудь полегче по алгоритмам и структурам данных, а потом приступить к Кормену, ну или гуглить по ходу прочтения, непонятно, что такое омега малая, ищем в гугле и т. д. Надеюсь, что я Вам помог.