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

Question

Я читаю главы 2 и 3 из CLRS и так часто зацикливаюсь, особенно в проблемах, приведенных в конце каждой главы, что я задаюсь вопросом, действительно ли это будет стоить для этих усилий. Я не могу понять решение в Интернете, как этот: http://clrs.skanev.com/02/problems/01.html

Я слышал, что эта книга является одной из самых популярных текстовых книг для университетского класса CS, но люди пропускают сложные детали и просто запоминают важные вещи, такие как сортировка вставки имеет ли этот порядок роста и сортировки сортировки тот порядок роста и идти вперед?

Разве это не достаточно, чтобы быть знакомым со многими полезными алгоритмами, чтобы иметь о таком же понимании информатики, как люди со степенью в CS вообще?

Answer 1

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

TL; доказательство того, что вы можете использовать знания, является способность решать проблемы, а проблемы с учебниками просты. ^‡ Не обойтись без другого.

‡ текстов Кнута является заметным исключением: он также предлагает некоторые пограничные трудноразрешимые проблемы, и все между ними :)

Answer 2

Делом в том, что «люди со степенью в CS ... в целом» может работы out порядок роста алгоритма. Это, почему люди идут на усвоение этого материала. Если вы просто хотите быть в состоянии сказать «mergesort is O (n log n)», то действительно, все, что вам нужно, это увидеть и запомнить этот факт. Если вы хотите иметь возможность выработать O() алгоритма, даже если он есть у вас никогда не видел до - вам нужны эти методы.