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

[Shador]

Упражнение 4

Используя суммирование членов арифметической прогрессии, докажите, что программа выше не только O( n^2 ), но так же и Θ( n^2 ). Если вы не знаете, что такое арифметическая прогрессия, то посмотрите в википедии — это не сложно.

Как понять? Речь же идёт о той горе-сортировке на Руби? Её алгоритм очевидно имеет О(n²), как она может быть выше?
Использование суммирования членов арифметической прогрессии — это как я понимаю, подсчёт суммарного количества итераций внутреннего цикла, которое равно n + (n-1) + (n-2) +… + 1, а то есть n(n-1)/2. Это и есть О(n²), или я что-то не так понял?

[inout]

Её алгоритм очевидно имеет О(n^2), как она может быть выше?

Это говорит о том, что наша программа асимптотически не хуже, чем n^2. Она будет работать или лучше, или также.

Показывая, что для данной сортировки Θ( n^2 ), мы показываем, что лучше она работать не будет:

n(n-1)/2 ∈ Θ(n^2).

[Shador]

В задании как раз просят доказать, что программа выше, что в терминологии статьи означает что её Θ > Θ( n^2 ). Это и вызвало недоумение.

[Nokta_strigo]

«Выше» — имеется ввиду выше по тексту.

[AveNat]

Да, речь идёт о сортировке на Руби. Автор просит доказать, что для неё Θ (точная оценка сложности) и O (верхний предел сложности) совпадают и являются n².

[boov]

Не хотелось бы выглядеть занудой, но сумма членов прогрессии все же будет n(n+1)/2

[Shador]

Да-да, просто на момент написания ошибочно думал что там сумма ряда от 1 до (n-1), а не до n.

[neru]

Имхо, есть на Хабре статьи поинформативнее и в то же время короче – ищется через удобный интерфейс. Ну, вот, например

[inout]

Один из первых комментариев под топиком:

чем полезная? проще научиться глядя на алгоритм, говорить какая у него комплексити (сложность?).
имхо, от таблицы один профит — алгоритм в мой голове «на уровне», или можно лучше?

и следом:

Научите меня? (напишите статью, как научиться в смысле). Прошел два курса, прослушал кучу лекций — я так и не понял как определяется сложность алгоритмов.

[neru]

А под одним из первых комментариев ещё комментарии. Кстати, это сообщение — комментарий о том, что под комментарием комментарий.

Чего сказать-то хотели? )))

[inout]

Из введения:

Многие нынешние программисты, пишущие классные и широко распространённые программы, имеют крайне смутное представление о теоретической информатике. Это не мешает им оставаться прекрасными творческими специалистами, и мы благодарны за то, что они создают.

Тем не менее, знание теории тоже имеет своё преимущества и может оказаться весьма полезным. В этой статье, предназначенной для программистов, которые являются хорошими практиками, но имеют слабое представление о теории, я представлю один из наиболее прагматичных программистских инструментов: нотацию «большое О» и анализ сложности алгоритмов. Также этот пост принесёт с собой понимание таких общих терминов, используемых теоретиками информатики, как «большое О», «асимптотическое поведение», «анализ наиболее неблагоприятного случая» и т.п.

У этой статьи и той, на которую вы сослались, разные назначения: одна дает информацию о сложности алгоритмов в сравнении, другая — показывает как эту сложность определять самостоятельно.

[neru]

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

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

[AveNat]

Это вы ещё третью и четвёртую не видели :) Материал действительно очень разжёван (как-никак, его ЦА — в основном школьники). Но повторю своё «от переводчика»: у меня после прочтения уложился весь ворох имевшейся ранее информации по оценке сложности алгоритмов. Не думаю, что я настолько уникальная личность, и надеюсь, что этот текст будет в этом плане полезен и ещё кому-то.

А статья по вашей ссылке — годная штука. Я её тоже в своё время нашла и в избранное добавила.

[equinox7]

Упражнение 3 из статьи, и решение:

Алгоритм с O( n ) имеет Θ( 1 ).
Может как быть, так и не быть истиной, зависит от алгоритма. В общем случае — это ложь. Если алгоритм является Θ( 1 ), то он, безусловно, и O( n ). Но если он O( n ), то может и не быть Θ( 1 ). Например, Θ( n ) алгоритм является O( n ), а Θ( 1 ) — нет.

Я что-то не понимаю или тут действительно противоречие в ответе? Сначала говорится

Если алгоритм является Θ( 1 ), то он, безусловно, и O( n )

и тут же

Θ( n ) алгоритм является O( n ), а Θ( 1 ) — нет

То, что условие не всегда истинно я понял, вроде. Не понятен сам ответ.

P.S. Не хватает ссылки на продолжение.