Вам бонус- начислено 1 монета за дневную активность. Сейчас у вас 1 монета

Анализ и оценка сложности алгоритмов, О большое, функции оценки сложности

Лекция



Сразу хочу сказать, что здесь никакой воды про сложность алгоритмов, и только нужная информация. Для того чтобы лучше понимать что такое сложность алгоритмов, оценка сложности алгоритмов, анализ сложности алгоритмов, большое o, доминирующий оператор, о большое, big o, рекурсивная сложность, логарифмическая сложность, сложность рекурсивных алгоритмов, функции оценки сложности, практическая оценка сложности алгоритмов , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

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

Вы действительно понимаете что такое о большое (Big O)? Если это так, то эта статья поможет вам освежить ваши знания перед собеседованием. Если нет, эта статья расскажет вам о том что это такое и зачем нужно об этом знать.

Нотация О большое является одним из самых фундаментальных инструментов анализа сложности алгоритма. Эта статья написана с предположением, что вы уже являетесь программистом и за вашими плечами большое количество написанного кода. Кроме того, для лучшего понимания материала потребуется знания основ математики средней школы. И так если вы готовы, давайте начнем!


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

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

Я надеюсь, что это текст будет полезен для тех программистов-практиков, у которых нет большого опыта в теоретической информатике (то, что самые вдохновленные инженеры-программисты никогда не ходили в колледж, уже давно свершившийся факт). Но поскольку статья предназначена и для студентов тоже, то временами она будет звучать, как учебник. Более того, некоторые темы могут показаться вам чересчур простыми (например, вы могли сталкиваться с ними во время своего обучения). Так что, если вы чувствуете, что понимаете их — просто пропускайте эти моменты. Другие секции идут несколько глубже и являются более теоретическими, потому что студенты, участвующие в соревнованиях, должны разбираться в теории алгоритмов лучше, чем средний практик. Но знать эти вещи не менее полезно, а следить за ходом повествования не так уж сложно, так что они, скорее всего, заслуживают вашего внимания. Оригинальный текст был направлен учащимся старшей школы, никаких особых математических знаний он не требует, поэтому каждый, имеющий опыт программирования (например, знающий, что такое рекурсия) способен понять его без особых проблем.

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

Нотация «большого О» и анализ сложности алгоритмов — это те вещи, которые и программисты-практики, и студенты-новички часто считают трудными для понимания, боятся или вообще избегают, как бесполезные. Но они не так уж сложны и заумны, как может показаться на первый взгляд. Сложность алгоритма — это всего лишь способ формально измерить, насколько быстро программа или алгоритм работают, что является весьма прагматичной целью. Давайте начнем с небольшой мотивации по этой теме.

Мотивация


Мы уже знаем, что существуют инструменты, измеряющие, насколько быстро работает код. Это программы, называемые профайлерами(profilers), которые определяют время выполнения в миллисекундах, помогая нам выявлять узкие места и оптимизировать их. Но, хотя это и полезный инструмент, он не имеет отношения к сложности алгоритмов. Сложность алгоритма — это то, что основывается на сравнении двух алгоритмов на идеальном уровне, игнорируя низкоуровневые детали вроде реализации языка программирования, «железа», на котором запущена программа, или набора команд в данном CPU. Мы хотим сравнивать алгоритмы с точки зрения того, чем они, собственно, являются: идеи, как происходит вычисление. Подсчет миллисекунд тут мало поможет. Вполне может оказаться, что плохой алгоритм, написанный на низкоуровневом языке (например, ассемблере) будет намного быстрее, чем хороший алгоритм, написанный языке программирования высокого уровня (например, Python или Ruby). Так что пришло время определиться, что же такое «лучший алгоритм» на самом деле.

Алгоритм — это программа, которая представляет из себя исключительно вычисление, без других часто выполняемых компьютером вещей — сетевых задач или пользовательского ввода-вывода. Анализ сложности позволяет нам узнать, насколько быстра эта программа, когда она совершает вычисления. Примерами чисто вычислительных операций могут послужить операции над числами с плавающей запятой (сложение и умножение), поиск заданного значения в находящейся в ОЗУ базе данных, определение игровым ИИ движения своего персонажа таким образом, чтобы он передвигался только на короткое расстояние внутри игрового мира, или запуск шаблона регулярного выражения на соответствие строке. Очевидно, что вычисления встречаются в компьютерных программах повсеместно.

Анализ сложности также позволяет нам объяснить, как будет вести себя алгоритм при возрастании входного потока данных. Если наш алгоритм выполняется одну секунду при 1000 элементах на входе, то как он себя поведет, если мы удвоим это значение? Будет работать также быстро, в полтора раза быстрее или в четыре раза медленнее? В практике программирования такие предсказания крайне важны. Например, если мы создали алгоритм для web-приложения, работающего с тысячей пользователей, и измерили его время выполнения, то используя анализ сложности, мы получим весьма неплохое представление о том, что случится, когда число пользователей возрастет до двух тысяч. Для соревнований по построению алгоритмов анализ сложности также даст нам понимание того, как долго будет выполняться наш код на наибольшем из тестов для проверки его правильности. Так что, если мы определим общее поведение нашей программы на небольшом объеме входных данных, то сможем получить хорошее представление и о том, что будет с ней при больших потоках данных. Давайте начнем с простого примера: поиска максимального элемента в массиве.

Подсчет инструкций


В этой статье для реализации примеров я буду использовать различные языки программирования. Не переживайте, если вы не знакомы с каким-то из них — любой, кто умеет программировать, способен прочитать этот код без особых проблем, поскольку он прост, и я не собираюсь использовать какие-либо экзотические фенечки языка реализации. Если вы — студент-олимпиадник, то, скорее всего, пишите на С++, поэтому у вас тоже не должно возникать проблем. В этом случае я также рекомендую прорабатывать упражнения, используя С++ для большей практики.

Максимальный элемент массива можно найти с помощью простейшего отрывка кода. Например, такого, написанного на Javascript. Дан входной массив А размера n:
var M = A[ 0 ];
 
for ( var i = 0; i < n; ++i ) {
    if ( A[ i ] >= M ) {
        M = A[ i ];
    }
}

Сначала подсчитаем, сколько здесь вычисляется фундаментальных инструкций. Мы сделаем это только один раз — по мере углубления в теорию такая необходимость отпадет. Но пока наберитесь терпения на то время, которое мы потратим на это. В процессе анализа данного кода, имеет смысл разбить его на простые инструкции — задания, которые могут быть выполнены процессором тотчас же или близко к этому. Предположим, что наш процессор способен выполнять как единые инструкции следующие операции:
  • Присваивать значение переменной
  • Находить значение конкретного элемента в массиве
  • Сравнивать два значения
  • Инкрементировать значение
  • Основные арифметические операции (например, сложение и умножение)

Мы будем полагать, что ветвление (выбор между if и else частями кода после вычисления if-условия) происходит мгновенно, и не будем учитывать эту инструкцию при подсчете. Для первой строки в коде выше:
var M = A[ 0 ]; 

требуются две инструкции: для поиска A и для присвоения значения M (мы предполагаем, что n всегда как минимум 1). Эти две инструкции будут требоваться алгоритму, вне зависимости от величины n. Инициализация цикла for тоже будет происходить постоянно, что дает нам еще две команды: присвоение и сравнение.
i = 0;
i < n;

Все это происходит до первого запуска for. После каждой новой итерации мы будем иметь на две инструкции больше: инкремент i и сравнение для проверки, не пора ли нам останавливать цикл.
++i;
i < n;

Таким образом, если мы проигнорируем содержимое тела цикла, то количество инструкций у этого алгоритма 4 + 2n — четыре на начало циклаfor и по две на каждую итерацию, которых мы имеем n штук. Теперь мы можем определить математическую функцию f(n) такую, что зная n, мы будем знать и необходимое алгоритму количество инструкций. Для цикла for с пустым телом f( n ) = 4 + 2n.

Анализ наиболее неблагоприятного случая


В теле цикла мы имеем операции поиска в массиве и сравнения, которые происходят всегда:
if ( A[ i ] >= M ) { ...

Но тело if может запускаться, а может и нет, в зависимости от актуального значения из массива. Если произойдет так, что A[ i ] >= M, то у нас запустятся две дополнительные команды: поиск в массиве и присваивание:
M = A[ i ]

Мы уже не можем определить f(n) так легко, потому что теперь количество инструкций зависит не только от n, но и от конкретных входных значений. Например, для A = [ 1, 2, 3, 4 ] программе потребуется больше команд, чем для A = [ 4, 3, 2, 1 ]. Когда мы анализируем алгоритмы, мы чаще всего рассматриваем наихудший сценарий. Каким он будет в нашем случае? Когда алгоритму потребуется больше всего инструкций до завершения? Ответ: когда массив упорядочен по возрастанию, как, например, A = [ 1, 2, 3, 4 ]. Тогда M будет переприсваиваться каждый раз, что даст наибольшее количество команд. Теоретики имеют для этого причудливое название — анализ наиболее неблагоприятного случая, который является ни чем иным, как просто рассмотрением максимально неудачного варианта. Таким образом, в наихудшем случае в теле цикла из нашего кода запускается четыре инструкции, и мы имеем f( n ) = 4 + 2n + 4n = 6n + 4.

Асимптотическое поведение


С полученной выше функцией мы имеем весьма хорошее представление о том, насколько быстр наш алгоритм. Однако, как я и обещал, нам нет нужды постоянно заниматься таким утомительным занятием, как подсчет команд в программе. Более того, количество инструкций у конкретного процессора, необходимое для реализации каждого положения из используемого языка программирования, зависит от компилятора этого языка и доступного процессору (AMD или Intel Pentium на персональном компьютере, MIPS на Playstation 2 и т.п. ) набора команд. Ранее же мы говорили, что собираемся игнорировать условия такого рода. Поэтому сейчас мы пропустим нашу функцию f через «фильтр» для очищения ее от незначительных деталей, на которые теоретики предпочитают не обращать внимания.

Наша функция 6n + 4 состоит из двух элементов: 6n и 4. При анализе сложности важность имеет только то, что происходит с функцией подсчета инструкций при значительном возрастании n. Это совпадает с предыдущей идеей «наихудшего сценария»: нам интересно поведение алгоритма, находящегося в «плохих условиях», когда он вынужден выполнять что-то трудное. Заметьте, что именно это по-настоящему полезно при сравнении алгоритмов. Если один из них побивает другой при большом входном потоке данных, то велика вероятность, что он останется быстрее и на легких, маленьких потоках. Вот почему мы отбрасываем те элементы функции, которые при росте n возрастают медленно, и оставляем только те, что растут сильно. Очевидно, что 4 останется 4 вне зависимости от значения n, а 6n наоборот будет расти. Поэтому первое, что мы сделаем, — это отбросим 4 и оставим только f( n ) = 6n.

Имеет смысл думать о 4 просто как о «константе инициализации». Разным языкам программирования для настройки может потребоваться разное время. Например, Java сначала необходимо инициализировать свою виртуальную машину. А поскольку мы договорились игнорировать различия языков программирования, то попросту отбросим это значение.

Второй вещью, на которую можно не обращать внимания, является множитель перед n. Так что наша функция превращается в f( n ) = n. Как вы можете заметить, это многое упрощает. Еще раз, константный множитель имеет смысл отбрасывать, если мы думаем о различиях во времени компиляции разных языков программирования. «Поиск в массиве» для одного ЯП может компилироваться совершенно иначе, чем для другого. Например, в Си выполнение A[ i ] не включает проверку того, что i не выходит за пределы объявленного размера массива, в то время как дляПаскаля она существует. Таким образом, данный паскалевский код:
M := A[ i ]

эквивалентен следующему на Си:
if ( i >= 0 && i < n ) {
    M = A[ i ];
}

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

Описанные выше фильтры — «отбрось все факторы» и «оставляй только наибольший элемент» — в совокупности дают то, что мы называемасимптотическим поведением. Для f( n ) = 2n + 8 оно будет описываться функцией f( n ) = n. Говоря языком математики, нас интересует предел функции f при n, стремящемся к бесконечности. Если вам не совсем понятно значение этой формальной фразы, то не переживайте — все, что нужно, вы уже знаете. (В сторону: строго говоря, в математической постановке мы не могли бы отбрасывать константы в пределе, но для целей теоретической информатики мы поступаем таким образом по причинам, описанным выше). Давайте проработаем пару задач, чтобы до конца вникнуть в эту концепцию.
Анализ и оценка сложности алгоритмов, О большое, функции оценки сложности
Найдем асимптотики для следующих примеров, используя принципы отбрасывания константных факторов и оставления только максимально быстро растущего элемента:
  1. f( n ) = 5n + 12 даст f( n ) = n.
    Основания — те же, что были описаны выше
  2. f( n ) = 109 даст f( n ) = 1.
    Мы отбрасываем множитель в 109 * 1 , но 1 по-прежнему нужен, чтобы показать, что функция не равна нулю
  3. f( n ) = n2 + 3n + 112 даст f( n ) = n2
    Здесь n2 возрастает быстрее, чем 3n, который, в свою очередь, растет быстрее 112
  4. f( n ) = n3 + 1999n + 1337 даст f( n ) = n3
    Несмотря на большую величину множителя передn, мы по прежнему полагаем, что можем найти еще больший n, поэтому f( n ) = n3 все еще больше 1999n (см. рисунок выше)
  5. f( n ) = n + sqrt( n ) даст f( n ) = n
    Потому что n при увеличении аргумента растет быстрее, чем sqrt( n )
Упражнение 1
  1. f( n ) = n6 + 3n
  2. f( n ) = 2n + 12
  3. f( n ) = 3n + 2n
  4. f( n ) = nn + n

Если у вас возникли проблемы с выполнением этого задания, то просто подставьте в выражение достаточно большое n и посмотрите, какой из его членов имеет большую величину. Все очень просто, не так ли?

Сложность


Из предыдущей части можно сделать вывод, что если мы сможем отбросить все эти декоративные константы, то говорить об асимптотике функции подсчета инструкций программы будет очень просто. Фактически, любая программа, не содержащая циклы, имеет f( n ) = 1, потому что в этом случае требуется константное число инструкций (конечно, при отсутствии рекурсии — см. далее). Одиночный цикл от 1 до n, дает асимптотику f( n ) = n, поскольку до и после цикла выполняет неизменное число команд, а постоянное же количество инструкций внутри цикла выполняется n раз.

Руководствоваться подобными соображениями менее утомительно, чем каждый раз считать инструкции, так что давайте рассмотрим несколько примеров на закрепление этого материала. Следующая PHP-программа проверяет, содержится ли в массиве A размера n заданное значение:


Такой метод поиска значения внутри массива называется линейным поиском. Это обоснованное название, поскольку программа имеет f( n ) = n (что означает «линейный» более точно, мы рассмотрим в следующем разделе). Инструкция break позволяет программе завершиться раньше, даже после единственной итерации. Однако, напоминаю, что нас интересует самый неблагоприятный сценарий, при котором массив A вообще не содержит заданное значение. Поэтому f( n ) = n по-прежнему.
Упражнение 2
Систематически проанализируйте, сколько инструкций необходимо для приведенной выше PHP-программы при наиболее неблагоприятном случае, чтобы затем вывести ее асимптотику (аналогично тому, как в первой части мы анализировали программу на Javascript). Должно получиться f( n ) = n.


Давайте рассмотрим программу на Python, которая складывает два значения из массива и записывает результат в новую переменную:
v = a[ 0 ] + a[ 1 ] 

Здесь у нас постоянное количество инструкций, следовательно, f( n ) = 1.

Следующая программа на C++ проверяет, содержит ли вектор (своеобразный массив) A размера n два одинаковых значения:
bool duplicate = false;
for ( int i = 0; i < n; ++i ) {
    for ( int j = 0; j < n; ++j ) {
        if ( i != j && A[ i ] == A[ j ] ) {
            duplicate = true;
            break;
        }
    }
    if ( duplicate ) {
        break;
    }
}


Два вложенных цикла дадут нам асимптотику вида f( n ) = n2.

Практическая рекомендация: простые программы можно анализировать с помощью подсчета в них количества вложенных циклов. Одиночный цикл в n итераций дает f( n ) = n. Цикл внутри цикла — f( n ) = n2. Цикл внутри цикла внутри цикла — f( n ) = n3. И так далее.

Если в нашей программе в теле цикла вызывается функция, и мы знаем число выполняемых в ней инструкций, то легко определить общее количество команд для программы целиком. Рассмотрим в качестве примера следующий код на Си:
int i;
for ( i = 0; i < n; ++i ) {
    f( n );
}

Если нам известно, что f( n ) выполняет ровно n команд, то мы можем сказать, что количество инструкций во всей программе асимптотически приближается к n2, поскольку f( n ) вызывается n раз.

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

А сейчас давайте переключимся на интересную систему обозначений, используемую теоретиками. Когда мы выясняем точную асимптотику f, мы говорим, что наша программа — Θ( f( n ) ). Например, в примерах выше программы Θ( 1 ), Θ( n2 ) и Θ( n2 ), соответственно. Θ( n )произносится как «тета от n». Иногда мы говорим, что f( n ) (оригинальная функция подсчета инструкций, включая константы) есть Θ( что-то ). Например, можно сказать, что f( n ) = 2n — это функция, являющаяся Θ( n ). В общем, ничего нового. Можно так же написать, что 2n ∈ Θ( n ), что произносится: «два n принадлежит тета от n». Пусть вас не смущает такая нотация: она просто говорит о том, что если мы посчитаем количество необходимых программе команд, и оно будет равно 2n, то асимптотика этого алгоритма описывается как n (что мы находим, отбрасывая константу). Имея данную систему обозначений, приведем несколько истинных математических утверждений:
  1. n6 + 3n ∈ Θ( n6)
  2. 2n + 12 ∈ Θ( 2n )
  3. 3n + 2n ∈ Θ( 3n )
  4. nn + n ∈ Θ( nn )

Кстати, если вы решили упражнение 1 из первой части, то это его правильный ответ.

Мы называем эту функцию (т.е. то, что пишем Θ( здесь )) временной сложностью, или просто сложностью нашего алгоритма.Таким образом, алгоритм с Θ( n ) имеет сложность n. Также существуют специальные названия для Θ( 1 ), Θ( n ), Θ( n2 ) и Θ( log( n ) ), потому что они встречаются очень часто. Говорят, что Θ( 1 ) — алгоритм с константным временем, Θ( n )линейный, Θ( n2 )квадратичный, а Θ( log( n ) )логарифмический (не беспокойтесь, если вы еще не знаете, что такое логарифм — скоро мы об этом поговорим).

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

Нотация «большое О»


В реальной жизни иногда проблематично выяснить точно поведение алгоритма тем способом, который мы рассматривали выше. Особенно для более сложных примеров. Однако, мы можем сказать, что поведение нашего алгоритма никогда не пересечет некой границы. Это делает жизнь проще, так как четкого указания на то, насколько быстр наш алгоритм, у нас может и не появиться, даже при условии игнорирования констант (как раньше). Все, что нам нужно — найти эту границу, а как это сделать — проще объяснить на примере.

В конце статьи еще подробнее рассмотрим это понятие

Наиболее известной задачей, которую используют при обучении алгоритмам, является сортировка. Дается массив A размера n (звучит знакомо, не так ли?), и нас просят написать программу, его сортирующую. Интерес тут в том что, такая необходимость часто возникает в реальных системах. Например, обозревателю файлов нужно отсортировать файлы по имени, чтобы облегчить пользователю навигацию по ним. Или другой пример: в видео игре может возникнуть проблема сортировки 3D объектов, демонстрируемых на экране, по их расстоянию от точки зрения игрока в виртуальном мире, чтобы определить, какие из них будут для него видимы, а какие — нет (это называется Visibility Problem). Сортировка также интересна тем, что для нее существует множество алгоритмов, одни из которых хуже, чем другие. Так же эта задача проста для определения и объяснения. Поэтому давайте напишем кусок кода, который будет сортировать массив.

b = []
n.times do
    m = a[ 0 ]
    mi = 0
    a.each_with_index do |element, i|
        if element < m
            m = element
            mi = i
        end
     end
     a.delete_at( mi )
     b << m
end

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

Этот метод называется сортировкой выбором. Сначала находится минимальный элемент массива (a в коде выше. Минимум обозначен как m, а его индекс — как mi), который помещается в конец нового массива (b в нашем случае) и удаляется из оригинального. Затем среди оставшихся значений снова находится минимум, добавляется в новый массив (который теперь содержит два значения) и удаляется из старого. Процесс повторяется, пока все элементы не будут перенесены из первоначального в новый массив, что будет означать конец сортировки. В нашем примере мы имеем два вложенных цикла. Внешний цикл «пробегает» n раз, а внутренний — по разу для каждого элемента массива a. Поскольку изначально a имеет n элементов и на каждой итерации мы удаляем один из них, то сначала внутренний цикл «прокручивается» nраз, потом n - 1, n - 2 и так далее, пока на последней итерации внутренний цикл не пройдет всего один раз.

Если рассматривать сумму 1 + 2 + ... + (n - 1) + n, то найти сложность этого кода будет несколько проблематично. Но мы можем найти для нее «верхний предел». Для этого мы изменим программу (можно мысленно, не трогая код), чтобы сделать ее хуже, чем она есть, а затем выведем сложность для того, что получилось. Тогда можно будет уверенно сказать, что оригинальная программа работает или также плохо, или (скорее всего) лучше.

Давайте теперь подумаем над тем, как нам изменить программу, чтобы упростить для нее вывод сложности. Не забывайте: мы можем только ухудшать ее (например, добавляя в код новые инструкции), чтобы наша оценка имела смысл для оригинальной программы. Очевидно, что мы можем изменить внутренний цикл программы, заставив его вычисляться n раз на каждой итерации. Некоторые из этих повторений буду бесполезны, но зато это поможет нам проанализировать сложность результирующего алгоритма. Если мы внесем это небольшое изменение, то наш новый алгоритм будет иметь Θ( n2), поскольку получим два вложенных цикла, каждый из которых выполняется ровно n раз. А если это так, то оригинальный алгоритм имеет O( n2 ). O( n2 ) произносится как «большое О от n в квадрате». Это говорит о том, что наша программа асимптотически не хуже, чем n2. Она будет работать или лучше, или также. Кстати, если код действительно имеет Θ( n2), то мы все еще говорим, что он O( n2 ). Чтобы лучше понять это, представьте, что изменение оригинальной программы меняет ее не сильно, делая лишь чуть-чуть хуже. Примерно как от добавления бесполезных инструкций в начало программы. Это изменит только константу в функции подсчета инструкций, которую мы проигнорируем в асимптотике. Таким образом, Θ( n2) для программы — это и O( n2 ) тоже.

А вот обратное верно не всегда. Например, любой код с Θ( n ) также и O( n2 ) в дополнение к O( n ). Если мы представим, что Θ( n )программа — это просто цикл for, который выполняется n раз, мы можем сделать его хуже, добавив внутрь еще один for, тоже повторяющийсяn раз. Это даст программу с f( n ) = n2. Обобщая: любая программа с Θ( a ) является O( b ) при b худшем, чем a. Заметьте также, что изменение не обязательно должно иметь смысл или создавать код, аналогичный исходному. Все, что от него требуется — увеличить количество инструкций по отношению к заданному n. Мы используем результат для подсчета инструкций, а не для решения проблемы.

Итак, говоря, что программа имеет O( n2 ), мы находимся в безопасности: анализ алгоритма показал, что он никогда не будет работать хуже, чем n2. Это дает нам хорошую оценку того, насколько быстра наша программа. Давайте прорешаем несколько примеров, чтобы вы получше освоились с новой нотацией.
Упражнение 3
Что из нижеследующего истинно?
  1. Алгоритм с Θ( n ) имеет O( n )
  2. Алгоритм с Θ( n ) имеет O( n2 )
  3. Алгоритм с Θ( n2 ) имеет O( n3 )
  4. Алгоритм с Θ( n ) имеет O( 1 )
  5. Алгоритм с O( 1 ) имеет Θ( 1 )
  6. Алгоритм с O( n ) имеет Θ( 1 )
Решение
  1. Истина, поскольку оригинальная программа имеет Θ( n ). Следовательно, O( n ) может быть достигнуто и без изменения программы
  2. Поскольку n2 хуже n, то это истина
  3. Поскольку n3 хуже n2, то это истина
  4. Поскольку 1 не хуже n, то это ложь. Если программа асимптотически использует n инструкций (линейное число), то мы не можем сделать ее хуже так, чтобы асимптотически ей требовалась всего 1 (константное число) инструкций.
  5. Истина, поскольку обе сложности одинаковые
  6. Может как быть, так и не быть истиной, зависит от алгоритма. В общем случае — это ложь. Если алгоритм является Θ( 1 ), то он, безусловно, и O( n ). Но если он O( n ), то может и не быть Θ( 1 ). Например, Θ( n ) алгоритм является O( n ), а Θ( 1 ) — нет.
Упражнение 4
Используя суммирование членов арифметической прогрессии, докажите, что программа выше не только O( n2 ), но так же и Θ( n2 ). Если вы не знаете, что такое арифметическая прогрессия, то посмотрите в википедии — это не сложно.


Поскольку О-сложность алгоритма представляет собой верхний предел его настоящей сложности, которую, в свою очередь, отображает Θ, то иногда мы говорим, что Θ дает нам точную оценку. Если мы знаем, что найденная нами граница не точна, то можем использовать строчное о, чтобы ее обозначить. Например, если алгоритм является Θ( n ), то его точная сложность — n. Следовательно, этот алгоритм O( n ) и O( n2 )одновременно. Поскольку алгоритм Θ( n ), то O( n ) определяет границу более точно. А O( n2 ) мы можем записать как о( n2 )(произносится: «маленькое o от n в квадрате»), чтобы показать, что мы знаем о нестрогости границы. Конечно, лучше, когда мы можем найти точные границы для нашего алгоритма, чтобы иметь больше информации о его поведении, но, к сожалению, это не всегда легко сделать.
Упражнение 5
Определите, какие из следующих границ строгие, а какие — нет.
  1. Θ( n ) алгоритм, для которого мы нашли O( n ), как верхнюю границу
  2. Θ( n2 ) алгоритм, для которого мы нашли O( n3 ), как верхнюю границу
  3. Θ( 1 ) алгоритм, для которого мы нашли O( n ), как верхнюю границу
  4. Θ( n ) алгоритм, для которого мы нашли O( 1 ), как верхнюю границу
  5. Θ( n ) алгоритм, для которого мы нашли O( 2n ), как верхнюю границу
Решение
  1. В этом случае Θ-сложность и O-сложность одинаковые, поэтому граница

продолжение следует...

Продолжение:


Часть 1 Анализ и оценка сложности алгоритмов, О большое, функции оценки сложности
Часть 2 Оптимальная сортировка - Анализ и оценка сложности алгоритмов, О большое,
Часть 3 Примеры - Анализ и оценка сложности алгоритмов, О большое, функции
Часть 4 Почему О большое может не имеет значения - Анализ и

См.также

А как ты думаешь, при улучшении сложность алгоритмов, будет лучше нам? Надеюсь, что теперь ты понял что такое сложность алгоритмов, оценка сложности алгоритмов, анализ сложности алгоритмов, большое o, доминирующий оператор, о большое, big o, рекурсивная сложность, логарифмическая сложность, сложность рекурсивных алгоритмов, функции оценки сложности, практическая оценка сложности алгоритмов и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов

создано: 2014-08-18
обновлено: 2021-05-03
133915



Рейтиг 2 of 10. count vote: 2
Вы довольны ?:


Найди готовое или заработай

С нашими удобными сервисами без комиссии*

Как это работает? | Узнать цену?

Найти исполнителя
$0 / весь год.
  • У вас есть задание, но нет времени его делать
  • Вы хотите найти профессионала для выплнения задания
  • Возможно примерение функции гаранта на сделку
  • Приорететная поддержка
  • идеально подходит для студентов, у которых нет времени для решения заданий
Готовое решение
$0 / весь год.
  • Вы можите продать(исполнителем) или купить(заказчиком) готовое решение
  • Вам предоставят готовое решение
  • Будет предоставлено в минимальные сроки т.к. задание уже готовое
  • Вы получите базовую гарантию 8 дней
  • Вы можете заработать на материалах
  • подходит как для студентов так и для преподавателей
Я исполнитель
$0 / весь год.
  • Вы профессионал своего дела
  • У вас есть опыт и желание зарабатывать
  • Вы хотите помочь в решении задач или написании работ
  • Возможно примерение функции гаранта на сделку
  • подходит для опытных студентов так и для преподавателей



Комментарии


Оставить комментарий
Если у вас есть какое-либо предложение, идея, благодарность или комментарий, не стесняйтесь писать. Мы очень ценим отзывы и рады услышать ваше мнение.
To reply

Алгоритмы и теория алгоритмов

Термины: Алгоритмы и теория алгоритмов