[Powered by Google Translate] Вы, наверное, слышали, как люди говорят о быстром и эффективном алгоритме для выполнения вашей конкретной задачи, но что именно это значит для алгоритма, чтобы быть быстрым или эффективным? Ну, это не говорит о измерения в реальном времени, как секунд или минут. Это потому, что компьютерная техника и программного обеспечения значительно варьироваться. Моя программа может работать медленнее, чем ваш, потому что я бегу его на старом компьютере, или потому что я, оказывается, играет онлайн-игра видео В то же время, которое коробления всю мою память, или я может быть запущена моя программа с помощью различных программ , который общается с машиной по-разному на низком уровне. Это все равно, что сравнивать яблоки и апельсины. Просто потому, что мой медленный компьютер занимает больше времени, чем ваш отдать ответ не означает, что у вас есть более эффективный алгоритм. 

Таким образом, поскольку мы не можем напрямую сравнить время работы программы в течение секунд или минут, как мы можем сравнить 2 различных алгоритмов независимо от их аппаратной или программной среде? Чтобы создать более универсальный способ измерения алгоритмической эффективности, ученых-компьютерщиков и математиков разработали концепции для измерения асимптотической сложности программы и обозначений называется "Большой Ohnotation" Для описания этого. Формальное определение является то, что функция F (X) работает на порядок д (х) если существует некоторый (х) значения х и ₀ некоторая константа, C, для которой F (X) меньше или равна что постоянное раза д (х) для всех х больше х ₀. 

Но не пугает формальное определение. Что это на самом деле означает меньше теоретической точки зрения? Ну, это в основном способ анализа как быстро время выполнения программы растет асимптотически. То есть, как размер входа увеличивается к бесконечности, Скажем, вы сортировки массива размером 1000 по сравнению с массив размера 10. Как выполнения вашей программы растут? Например, представьте себе подсчета количества символов в строке самый простой способ  пешком через всю строку Письмо за письмом и добавления 1 к счетчику для каждого символа. Этот алгоритм, как говорят, работают в линейном времени по отношению к количеству символов, 'N' в строке. Короче говоря, он работает в O (N). Почему это происходит? Ну, при таком подходе, время, необходимое пройти всю строку пропорциональна количеству символов. Подсчет количества символов в 20-символьной строки собирается взять в два раза дольше, как это имеет для подсчета символов в 10-символьной строки, потому что вы должны смотреть на все символы и каждый символ занимает столько же времени, чтобы смотреть на. По мере увеличения количества символов, среда выполнения будет линейно возрастать с входной длины. 

А теперь представьте, если вы решите, что линейное время, О (п), просто не был достаточно быстр для Вас? Может быть, вы хранения огромных строк, и вы не можете позволить себе дополнительное время, которое потребуется , чтобы обойти все их характеры считая один-на-один. Итак, вы решили попробовать что-то другое. Что делать, если случилось бы уже хранятся количество символов в строке, скажем, в переменную под названием «Лена», на раннем этапе программы, прежде чем вы даже хранится самый первый символ в строке? Тогда все что вам придется сделать сейчас, чтобы узнать длину строки, это проверить, что значение переменной. Вам не придется смотреть на саму строку на всех, и доступа к значению переменной, как лен считается асимптотически постоянное время операции, или O (1). Почему это происходит? Ну, помните, что асимптотическая сложность означает. Как выполнения изменений, как размер Вашего входа растет? 

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

Конечно, есть недостаток. Вы тратите дополнительное пространство памяти компьютера хранения переменной и дополнительное время, необходимое вам сделать фактического хранения переменной, но дело до сих пор стоит, выяснить, как долго ваша строка была не зависит от длины строки на всех. Таким образом, он работает в O (1) или постоянной времени. Это, конечно, не означает, что ваш код выполняется в 1 шаге, но независимо от того, сколько шагов он, если он не меняется с размером входа, она по-прежнему асимптотически постоянным, которую мы представляем, как O (1). 

Как вы можете догадаться, Есть много различных больших O измерить время автономной работы алгоритмов. О (п) ² алгоритмы асимптотически медленнее, чем O (N) алгоритмов. То есть, как число элементов (N) растет, в конечном итоге O (п) ² алгоритмов займет больше времени чем O (N) алгоритмы для запуска. Это не означает, что О (п) алгоритмы всегда работать быстрее чем O (N) ² алгоритмы, даже в той же среде, на том же оборудовании. Может быть, для небольших размерах ввода,  О (п) ² алгоритм может на самом деле работать быстрее, но, в конце концов, в качестве входных размер увеличивается к бесконечности, О (п) ² алгоритма выполнения в конечном итоге затмить время работы O (п) алгоритм. Как и любой квадратичной математические функции  в конечном итоге обогнать любой линейной функции, независимо от того, сколько фору линейная функция начинается с. Если вы работаете с большими объемами данных, Алгоритмы, работающие в O (п) ² Время действительно может в конечном итоге замедляет работу программы, но для небольших размерах вход, Вы, вероятно, даже не заметят. 

Другой асимптотической сложности, логарифмическое время, O (журнал N). Примером алгоритма, который управляет этим быстро это классический алгоритм бинарного поиска, для нахождения элемента в уже отсортированный список элементов. 

Если вы не знаете, что бинарный поиск делает, Я объясню это для вас очень быстро. Допустим, вы ищете номер 3 В этом массиве целых чисел. Он смотрит на середину элемента массива и спрашивает: "Является ли элемент я хочу больше, равно или меньше, чем это?" Если он равен, то велик. Вы нашли элемент, и вы сделали. Если она больше, то вы знаете, элемент должен быть в правой части массива, и вы можете только смотреть на это в будущем, а если меньше, то вы знаете, что должно быть в левую сторону. Этот процесс повторяется с меньшим размером массива пока правильный элемент не найден. 

Это мощный алгоритм сокращает размер массива в два раза с каждой операции. Таким образом, чтобы найти элемент в упорядоченный массив размером 8, не более (войти ₂ 8), или 3 из этих операций, проверка среднего элемента, то резка массива в два раза будет необходимо, в то время как массив размером 16 имеет (вход ₂ 16), или 4 операции. Вот только еще 1 операцию для удвоил размер массива. Удвоение размера массива увеличивает время выполнения только 1 кусок этого кода. Опять же, проверка среднего элемента списка, то расщепление. Так вот, он сказал, чтобы работать в логарифмическое время, O (журнал N). Но подождите, вы говорите, разве это не зависит от того, где в списке элемент, который вы ищете есть? Что делать, если первый элемент вы посмотрите на случается, правильно? Тогда, это займет всего 1 операцию, независимо от того, насколько большой список. 

Ну, вот почему ученые-компьютерщики больше терминов асимптотической сложности, которые отражают лучшем случае и наихудший выступления алгоритм. Более правильно, верхняя и нижняя границы на время выполнения. В лучшем случае для двоичного поиска, наш элемент прямо там, в середине, , и вы получите его в постоянное время, независимо от того, насколько большой остальной части массива. Символ, используемый для этого Ω. Таким образом, этот алгоритм называется работать в Ω (1). В лучшем случае, она находит элемент быстро, независимо от того, насколько большой массив, а в худшем случае, он должен выполнить (§ п) раскол проверки массива, чтобы найти правильный элемент. Худший верхней границы называют с большой "О", что вы уже знаете. Таким образом, это O (журнал N), но Ω (1). 

Линейный поиск, напротив, , в котором вы идете через каждый элемент массива , чтобы найти тот, который вы хотите, в лучшем случае Ω (1). Опять же, первый элемент, который вы хотите. Таким образом, это не имеет значения, насколько большой массив. В худшем случае, это последний элемент в массиве. Таким образом, вы должны идти через все п элементов в массиве, чтобы найти его, Например, если вы искали 3. Таким образом, он работает в O (п) потому что это пропорционально количеству элементов в массиве. 

Еще один символ используется Θ. Это может быть использовано для описания алгоритмов, где лучшие и худшие случаи то же самое. Это касается в строку длиной алгоритмов мы говорили ранее. То есть, если мы сохраняем его в переменной перед мы храним строки и доступ к нему позже в постоянное время. Независимо от того, какой номер Мы хранение в эту переменную, мы должны смотреть на это. В лучшем случае, мы смотрим на это и найти длину строки. Так что Ω (1) или лучшем случае постоянной времени. В худшем случае, мы смотрим на него и найти длину строки. Таким образом, O (1) или постоянной времени в худшем случае. Таким образом, поскольку в лучшем случае, а худшем случае такие же, это, можно сказать, работают в Θ (1) времени. 

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

Если вы работаете в O (п) ² алгоритм, или еще хуже, O (2 ⁿ) алгоритм, одним из наиболее быстро растущих типов, Вы действительно начинаете замечать замедление когда вы начинаете работать с большими объемами данных. 

Вот асимптотической сложности. Спасибо.