Введение в анализ сложности алгоритмов (часть 1)

[@oshibka404]

«Мягкое введение» звучит стократно ярче, чем «Gentle Introduction».

[@geakstr]

Гы гы, Бивис, он сказал «введение».

[@AveNat]

Самой смешно, но как это адекватно перевести — ума не приложу. Полагаете, правильнее оставить английский вариант?

[@marshinov]

Нормально-нормально, оставьте. Я вот только после этого комментария улыбнулся.

[@tick]

А знаете, почему смешно? Потому что привычная сочетаемость нарушена.
В академическом русском «Введение в» в начале заглавия привычно и приемлимо. Но вы нарушили устоявшуюся формулу, добавив прилагательное. Сравните со словом «член». Сказать «член совета», «член-корреспондент» нормально, никто не ухмыльнётся. А «важный член совета» — уже как-то не то. И разумеется, никогда-никогда не говорите «большой член-корреспондент» :)

Заменить «введение» можно на «основы» или «начала». Gentle можно перевести и как «легкий», «простой» или даже в данном контексте «доступный».

[@AveNat]

Спасибо за пояснение. Решила не множить сущности и оставить просто «Введение».

[@olegchir]

Учитывая текст, который идет дальше, «мягкое введение» звучит в самый раз!

[@Indexator]

Чтобы совсем все не усложнять, можно просто заменить слово «введение», например, словом «знакомство» с любыми прилагательными))

[@sysmetic]

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

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

[@AveNat]

А вот про «галочку» сразу и не сообразила. Спасибо!

[@Seter17]

вопрос к автору — скажите, а вы не планируете цикл статей с анализом известных алгоритмов и описанием различных техник анализа? Типа «Amortized analysis» и т.д. (извините, не знаю точного русского перевода)

[@CAH4A]

Это перевод.
Спросите лучше тут: discrete.gr/complexity/

[@Seter17]

аррр. давно просих хабр сделать надписть «перевод» больше и заметнее. Извиняюсь

[@Singerofthefall]

Простите, но куда уж заметнее =))

[@Seter17]

я бы значок перевода сделал бы позаметнее и побольше =) но опять же, никто не отменяет мою вечную невнимательность.

[@mthps]

Алгоритм — это программа, которая представляет из себя исключительно вычисление...

Какое в Греции забавное определение алгоритма.

[@wasil]

Тоже при прочтении сразу бросилось в глаза

[@amarao]

Вот за это я и не люблю CS-гиков. Считают, что в оценке эффективности алгоритма важным является только старший член (то есть o(n), а константы/множители пофигу). А в жизни есть стопятьсот случаев, когда константы куда важнее асимптотики, потому что они определяют как быстро система отреагирует на изменения. Но куда там, до плебейских констант infinity-патрициям…

[@MuLLtiQ]

Константы влияют, и их, конечно, нужно оптимизировать. Но если алгоритм — отстой, то тут никакие константы не спасут.

[@amarao]

Есть множество случаев, когда константа оказывается больше, чем практически любое O(что-то(n)), потому что для запуска нужно, допустим, три миллиарда тактов, а алгоритм O(n). А рядом нечто, что запускается за пару миллионов тактов, но использует O(n!). Если у нас n оказывается в диапазоне ~10, то второй вариант выгоднее, не смотря на асимпотику в стиле «выноси всех живых».

[@MuLLtiQ]

При таком разбросе инициализацию также стоит учитывать при анализе асимптотики алгоритма, а не отбрасывать как константу.

Ну и если придираться: 10! = 3628800, что в 362 тыс. 880 раз больше чем 10. Простите :)

[@Shador]

Если бы вместо

for ( var i = 0; i < n; ++i ) {
...
}

там было

for ( var i = 1; i < n; ++i ) {
...
}

, тело цикла в worst case scenario выполнялось бы только n-1 раз, следовательно количество операций вышло бы 4 + 2n + 4(n-1) = 6n.
Что гораздно элегантнее, правда возможно менее наглядно.

[@Shador]

Да уж, лучше без пробелов между минусом и его операндами, чем тире вместо минуса.

[@ZyXI]

Лучше тогда возьмите таблицу символов и напишите минус. То, что выше, — называется «дефисоминус» (U+002D — это HYPHEN-MINUS (PDF на unicode.org)), а не минус и не дефис. Или обрамляйте формулы в <code></code>, как обычно делаю я:

4 + 2n + 4(n − 1) = 6n — вариант с минусом.
4 + 2n + 4(n - 1) = 6n — вариант с <code></code>.
4 + 2n + 4(n − 1) = 6n — вариант и с тем, и с другим.

+-−
+−- — сравнение (первым идёт дефисоминус, все соседние чёрточки различаются).

+-−
+−- — сравнение для <code></code>.

На habrahabr в комментариях такой шрифт, что дефисоминус и минус на одном уровне, но вот так у меня в textarea: . Для шрифтов, не предназначенных для набора программ, такая разница — самое обычное дело. Но горизонтальная черта в плюсе и в минусе всегда находится на одном уровне + минус всегда имеет ширину цифры (плюса) (конечно, зависит от шрифта, но это общепринятые нормы).

[@ZyXI]

На habrahabr в комментариях такой шрифт, что дефисоминус и минус на одном уровне

Кто‐нибудь мне объяснит, зачем в предпросмотре было делать другой шрифт?

textarea: .
Комментарий: .
Предпросмотр: .

[@iago]

продолжайте, пожалуйста, очень полезная статья! Я уже много лет интуитивно понимаю вещи, связанные со сложностью алгоритмов, но прочитать теорию, настолько доступно написанну — всегда только на пользу.

[@dokable]

А еще перевод можно отправить Dionysis Zindros. Он их добавляет к статье.