| Главная » Статьи » Java » Java Ranger Basic |
День 10/21
| Big O notation, Big Theta Notation В реальности нотаций шесть – строчные O, Θ, Ω, и прописные o, θ и ω. Но мы будем рассматривать только O и Θ. Представим, что у нас есть сортированный массив элементов, в котором миллион элементов. Какое-то конкретное значение мы можем искать линейным поиском – по циклу сравнить каждый элемент массива с нашим ключом. С другой стороны, поскольку массив отсортирован, мы можем искать бинарным поиском, который намного лучше. Big O и Big Theta – это формализм, который позволяет это лучше описать. Формализм – в смысле, что это не глубокая теория, а некоторый способ размышления и способ записи. Но в реальной жизни на сложных задачах этот формализм не всегда применим. Каждый алгоритм может потреблять много разных ресурсов. Обычно обращают внимание на две вещи – память и процессорное время. Процессорное время: например, для прохождения циклом по массиву из миллиона элементов при процессоре с одним ядром и тактовой частотой в 1 ГГц, тогда можно сказать, что мы на 1 / 1000 долю секунды полностью загрузим процессор. То есть мы можем этот метод вызывать всего лишь 1000 раз в секунду. С другой стороны, память, в нашем примере мы используем ее очень мало – хоть массив и большой, но в памяти нужно будет держать лишь одну созданную нами переменную – счетчик цикла. Бывают очень требовательные к памяти алгоритмы. Например, мы даем массив, а алгоритм перебирает все пары, при этом он создает квадратную матрицу. И если мы ему дадим массив на 100 элементов, он создает матрицу 100 х 100 – на 10000 элементов. Таким образом получается, что этот алгоритм с мегабайтным массивом вообще не сможет работать, потому что ему потребуется 1000 гигабайт памяти. Алгоритмы могут потреблять и другие ресурсы, например, шину данных. Яркий пример – System.arraycopy из памяти на жесткий диск, он просто гоняет данные с одного места в другое, процессор при этом будет загружен минимально. Поэтому, когда говорят про сложность алгоритма, всегда нужно говорить, о каком ресурсе речь. Обычно рассматривают потребление памяти и процессора. У каждого вызова алгоритма определяют какой-то характерный параметр или набор параметров задачи, который характеризует размер задачи. Например, метод sort() может получать разной длины массивы int. Поэтому задачи, где один аргумент – массив, характеризуются длиной массива. Размер задачи обычно обозначают функциональным символом N. Рассмотрим на примере потребления процессора. Мы хотим записать время работы наших алгоритмов (методов), как функцию от размера аргумента N. И тогда окажется, что время работы сортировок пузырьком, слиянием и выбором – N2, так как размер массива N, а мы запускаем двойной вложенный цикл по размеру массива, при этом в худшем случае тело внутреннего цикла выполняется квадрат элементов раз. Если у нас линейный поиск (при котором у нас есть массив и ключ, и мы ищем, есть ли в этом массиве ключ), то можно сказать, что время работы будет N, так как мы запускаем цикл, который идет по массиву и сравниваем ключ с элементом массива. Если нашел, то линейный поиск возвращает индекс. Таким образом, если элемент найден сразу, то время поиска будет 1 – лучший случай. Худший случай – нашего элемента нет в массиве, придется пройти по всему массиву и тогда время – N. В реальной жизни всегда приходится говорить о среднем случае, но его всегда сложнее всего рассматривать, потому что не всегда ясно, по каким данным следует усреднять. Например, вопрос о среднем времени работы сайта интернет-магазина: тестировщики выбирают какие-то ключевые страницы (главную, страницу регистрации, истории покупок), пишут нагрузочные тесты и выясняют, сколько эти страницы воспроизводятся (рендерятся) для среднего пользователя. Но могут быть отдельные пользователи, которые совершили миллион покупок, тогда некоторые страницы (истории поиска) будут для них очень долго рендериться, или когда будет рассчитываться скидка для таких пользователей, или попадает ли он под данную акцию – возможно алгоритм такой, что все записи надо будет перебрать. Тогда в реальной жизни этих усредненных пользователей приходится создавать. При анализе алгоритмов часто интересует худшая ситуация, худший случай – весьма показательный. В лучшем случае и при линейном, и при бинарном поисках время будет 1. В худшем же – у линейного N, у бинарного – log2(N). Например, рост человека может находиться в интервале между 179 см и 181 см, меняясь в течении суток. При этом у нас есть точная нижняя граница (179) и точная верхняя граница (181). Есть просто верхняя граница (>181) – любое число, которое больше точной верхней границы, верхних границ много. И нижних границ (<179) также много. Можно сказать, что точная нижняя граница – это максимальная нижняя граница, а точная верхняя граница – наименьшая из верхних границ. Так вот если в этом ключе рассматривать время работы алгоритма, то строчные буквы O, Θ и Ω отвечают за правую часть (верхнюю границу), а прописные буквы o, θ и ω – за левую часть (нижнюю границу). А именно – за точные границы отвечают O (за точную верхнюю) и o (за точную нижнюю), любая верхняя граница – Θ. Вообще говоря, нам нужна O, но в жизни мы чаще находим Θ и не знаем, это точная верхняя оценка или нет. Когда говорится N, то имеется в виду N каких-то абстрактных математических действий. Умножение, деление, сложение, вычисление синуса, if – это все одно действие, один такт. Обычно говорят о порядке величины, поэтому принимают, что O(N) = O(c * N). Например, время линейного поиска может быть 17N, а на другом процессоре 3N, на третьем процессоре с другим компилятором – 9N. Можно сказать, что O(3N) = O(2N). Поэтому говорят, что линейный поиск занимает O(N). Если мы считаем O(f + g), и на бесконечности одна из этих функций бесконечно больше второй функции, то второй функцией можно пренебречь. Также можно пренебречь константой. Например, O(N2/200 + N/2) = O(N2/200) = O(N2) – здесь одна квадратичная функция, а вторая линейная. Книга по теме: Кнут – Конкретная математика. Основание информатики, стр. 481. Книги по алгоритмам: Вирт – Алгоритмы и структуры данных. Классика уже лет 30, Вирт – автор двух языков программирования. Томас Кормен – Алгоритмы. Построение и анализ. В конце концов желательно прочитать за год, два, пять. Это учебник по теории алгоритмов для младших курсов Массачусетского технологического института (одного из ведущего в мире института по программированию. Второй – Стэндфордский университет.). В следующей теме мы рассмотрим: Binary Search Источник: http://becomejavasenior.com/courses/?utm_source=Java+Email+Courses&utm_campaign=aa710df388-JavaRangerBasicIntro&utm_medi | |
| Просмотров: 358 | | |
| Всего комментариев: 0 | |