Comments 16
Упражнение 4
Используя суммирование членов арифметической прогрессии, докажите, что программа выше не только O( n^2 ), но так же и Θ( n^2 ). Если вы не знаете, что такое арифметическая прогрессия, то посмотрите в википедии — это не сложно.
Как понять? Речь же идёт о той горе-сортировке на Руби? Её алгоритм очевидно имеет О(n2), как она может быть выше?
Использование суммирования членов арифметической прогрессии — это как я понимаю, подсчёт суммарного количества итераций внутреннего цикла, которое равно n + (n-1) + (n-2) +… + 1, а то есть n(n-1)/2. Это и есть О(n2), или я что-то не так понял?
Её алгоритм очевидно имеет О(n^2), как она может быть выше?
Это говорит о том, что наша программа асимптотически не хуже, чем n^2. Она будет работать или лучше, или также.
Показывая, что для данной сортировки Θ( n^2 ), мы показываем, что лучше она работать не будет:
n(n-1)/2 ∈ Θ(n^2).
Да, речь идёт о сортировке на Руби. Автор просит доказать, что для неё Θ (точная оценка сложности) и O (верхний предел сложности) совпадают и являются n2.
Не хотелось бы выглядеть занудой, но сумма членов прогрессии все же будет n(n+1)/2
Имхо, есть на Хабре статьи поинформативнее и в то же время короче – ищется через удобный интерфейс. Ну, вот, например
Один из первых комментариев под топиком:
и следом:
чем полезная? проще научиться глядя на алгоритм, говорить какая у него комплексити (сложность?).
имхо, от таблицы один профит — алгоритм в мой голове «на уровне», или можно лучше?
и следом:
Научите меня? (напишите статью, как научиться в смысле). Прошел два курса, прослушал кучу лекций — я так и не понял как определяется сложность алгоритмов.
А под одним из первых комментариев ещё комментарии. Кстати, это сообщение — комментарий о том, что под комментарием комментарий.
Чего сказать-то хотели? )))
Чего сказать-то хотели? )))
Из введения:
У этой статьи и той, на которую вы сослались, разные назначения: одна дает информацию о сложности алгоритмов в сравнении, другая — показывает как эту сложность определять самостоятельно.
Многие нынешние программисты, пишущие классные и широко распространённые программы, имеют крайне смутное представление о теоретической информатике. Это не мешает им оставаться прекрасными творческими специалистами, и мы благодарны за то, что они создают.
Тем не менее, знание теории тоже имеет своё преимущества и может оказаться весьма полезным. В этой статье, предназначенной для программистов, которые являются хорошими практиками, но имеют слабое представление о теории, я представлю один из наиболее прагматичных программистских инструментов: нотацию «большое О» и анализ сложности алгоритмов. Также этот пост принесёт с собой понимание таких общих терминов, используемых теоретиками информатики, как «большое О», «асимптотическое поведение», «анализ наиболее неблагоприятного случая» и т.п.
У этой статьи и той, на которую вы сослались, разные назначения: одна дает информацию о сложности алгоритмов в сравнении, другая — показывает как эту сложность определять самостоятельно.
Ну, во-первых, ссылка была на одну ИЗ статей. Нашёл я её за 3 секунды, просмотрел и на этом остановился. Вполне возможно, в других статьях тоже более подробно останавливаются на собственно методике оценки сложности алгоритмов. И в комментариях есть отсылки к пособиям.
Во-вторых, я выразил своё субъективное мнение, что в обсуждаемой нами здесь статье в двух частях очень много лишнего. Уж не знаю, стоит ли устраивать по этому поводу дискуссию. Переубедить Вам меня будет сложно да и не понятно зачем.
Во-вторых, я выразил своё субъективное мнение, что в обсуждаемой нами здесь статье в двух частях очень много лишнего. Уж не знаю, стоит ли устраивать по этому поводу дискуссию. Переубедить Вам меня будет сложно да и не понятно зачем.
Это вы ещё третью и четвёртую не видели :) Материал действительно очень разжёван (как-никак, его ЦА — в основном школьники). Но повторю своё «от переводчика»: у меня после прочтения уложился весь ворох имевшейся ранее информации по оценке сложности алгоритмов. Не думаю, что я настолько уникальная личность, и надеюсь, что этот текст будет в этом плане полезен и ещё кому-то.
А статья по вашей ссылке — годная штука. Я её тоже в своё время нашла и в избранное добавила.
А статья по вашей ссылке — годная штука. Я её тоже в своё время нашла и в избранное добавила.
UFO just landed and posted this here
Упражнение 3 из статьи, и решение:
Я что-то не понимаю или тут действительно противоречие в ответе? Сначала говорится
То, что условие не всегда истинно я понял, вроде. Не понятен сам ответ.
P.S. Не хватает ссылки на продолжение.
Алгоритм с O( n ) имеет Θ( 1 ).
Может как быть, так и не быть истиной, зависит от алгоритма. В общем случае — это ложь. Если алгоритм является Θ( 1 ), то он, безусловно, и O( n ). Но если он O( n ), то может и не быть Θ( 1 ). Например, Θ( n ) алгоритм является O( n ), а Θ( 1 ) — нет.
Я что-то не понимаю или тут действительно противоречие в ответе? Сначала говорится
Если алгоритм является Θ( 1 ), то он, безусловно, и O( n )и тут же
Θ( n ) алгоритм является O( n ), а Θ( 1 ) — нет
То, что условие не всегда истинно я понял, вроде. Не понятен сам ответ.
P.S. Не хватает ссылки на продолжение.
Sign up to leave a comment.
Введение в анализ сложности алгоритмов (часть 2)