LINUX.ORG.RU

Где почитать/потренироваться в сложности алгоритмов

 


2

2

Посоветуйте пожалуйста ресурс/статьи/книжку где можно подробно и углубленно почитать про сложность алгоритмов (О-нотация), а также потренироваться на нестандартных задачках и алгоритмах.
Большинство ссылок в гугле выдает готовые значения сложности для популярных алгоритмов, притом обычно ссылаются на О (оценка сверху - наихудший случай). Как показывает практика знание о (оценка снизу - наилучший случай) и усредненная оценка тоже требуется.

★★★

Ответ на: комментарий от Harald

Интересно, многие ли этот талмуд хотя бы пролистали (добровольно). Или это стандартный совет типа «Кнут».

ZweiStein ★☆ ()
Ответ на: комментарий от ZweiStein

Я больше половины прочитал. Кнута пролистывал

Harald ★★★★★ ()
Ответ на: комментарий от Harald

И как? Книга даёт что-то полезное или это просто учебник с кучей странной информации нужной студентам для сдачи экзамена?

ZweiStein ★☆ ()

о (оценка снизу - наилучший случай)

Точно?

Small O, Small Oh
f is dominated by g asymptotically
∀ k > 0, ∃ n0, ∀ n > n0, |f(n)| < k⋅g(n)

Оценка снизу — это омега.

В Кнуте есть, он же это и придумал, но читать его непросто, зато углубленно. Оно в самом начале первого тома, там в принципе математическое введение, но можно только нужную часть глянуть (и читать другое до прояснения). Пример на его языке там тоже есть.

xaizek ★★★★★ ()
Ответ на: комментарий от Harald

Хм. Это был совершенно нормальный вопрос. Без сарказма или чего-то подобного.

ZweiStein ★☆ ()
Ответ на: комментарий от xaizek

Спасибо! Но это программа максимум. А что-то более конспектное?

LIKAN ★★★ ()
Ответ на: комментарий от Harald

Добивил в ToRead лист. А что-то вроде выдержек, коспекта, есть?

LIKAN ★★★ ()
Ответ на: комментарий от LIKAN

ты хотел

где можно подробно и углубленно почитать про сложность алгоритмов (О-нотация)

вот берёшь и читаешь главу из Кормена, всю книгу необязательно

Harald ★★★★★ ()
Ответ на: комментарий от ZweiStein

Если ее читать подряд от корки до корки — может и не дает.

buddhist ★★★★★ ()
Ответ на: комментарий от LIKAN

подробно и углубленно

что-то более конспектное?

Надо бы определиться. Да и то введение у Кнута страниц на 150 в целом (там ещё страницы на упражнения и разделы со звёздочкой уходят), нужная часть меньше.

Можно ещё поискать лекции по алгоритмам и там глянуть. Вон, хоть на видео (не смотрел): https://youtu.be/o9nW0uBqvEo

Но «подробно и углубленно» оно обычно в книгах к этим курсах, всё равно. Если действительно хочется понять, то не надо их избегать.

xaizek ★★★★★ ()
Ответ на: комментарий от xaizek

Я с вами согласен - если есть время, то книги (или их части) - конечно лучше. Только вот время есть не всегда =(

LIKAN ★★★ ()

* Учебник по матанализу для первых курсов математических специальностей. Там в первом семестер будут пределы и нотации O(n) и o(n).
* Роберт Лафоре «Структуры данных и алгоритмы в Java»

trex6 ★★★★★ ()
Ответ на: комментарий от LIKAN

Если смотреть по изданию из https://e-maxx.ru/bookz/files/cormen.pdf то главы 1 (мат основы), 2 (сортировки), 3 (структуры), 4 (можно без матроидов), 5 (вычеркнуть 20, 21, 28, 29, 30) - теормин профессии, нужно хотя бы раз выучить и закодить, если не хочешь быть вебмакакой. Ещё нужно не забывать прочитывать задачки - в некоторых из них самый сок.

snizovtsev ★★★ ()
Ответ на: комментарий от snizovtsev

Да, не нужно, разумеется, это всё читать последовательно. Изучай параллельно все главы, по необходимости прыгая между ними когда что-то непонятно. Первые разделы проще последующих в каждой главе.

snizovtsev ★★★ ()
Ответ на: комментарий от ZweiStein

Прочитал больше половины, заглядываю иногда по мере надобности.

Makhno ()

Книги Седжвика Алгоритмы на С++ и Алгоритмы на Жава. По второй книге двухсерийный курс на Курсере, самый лучший на курсере, если что...

anto215 ★★ ()

«Анализ алгоритмов. Активный обучающий подход», автор вроде бы Макконнелл.

DELIRIUM ★★★★★ ()
Ответ на: комментарий от anto215

Седжвик хорош, но им можно от гопников отбиваться, лишние 15кг в рюкзаке я бы таскать не стал.

DELIRIUM ★★★★★ ()
Ответ на: комментарий от ZweiStein

И как? Книга даёт что-то полезное или это просто учебник с кучей странной информации нужной студентам для сдачи экзамена?

Прочитал/прорешал большую часть книги уже не будучи студентом.

orm-i-auga ★★★★★ ()

acm.timus.ru

получил Time limit exception? Значит твой алгоритм слишком сложный. Идеально для тренировки ;)

leetcode местами тоже поможет

OxiD ★★★ ()
Закрыто добавление комментариев для недавно зарегистрированных пользователей (со score < 50)