Введение в нотацию Big O в структуре данных
Введение в нотацию Big O в структуре данных
Нотация Big O – одна из самых необходимых математических нотаций, используемых в информатике для измерения эффективности алгоритма. Мы можем проанализировать эффективность алгоритма по количеству времени, памяти и других ресурсов, необходимых для выполнения алгоритма, и по изменению размера входных данных. Нотация Big O в структуре данных говорит нам, насколько хорошо алгоритм будет работать в конкретной ситуации. Другими словами, она дает верхнюю границу времени выполнения алгоритма или его наихудшую сложность.
PCP в ИИ и машинном обучении
Введение в асимптотические обозначения
Производительность алгоритма может меняться при изменении размера входных данных. Именно здесь в игру вступают асимптотические нотации, такие как нотация Big O. Асимптотические нотации позволяют описать время работы алгоритма, когда входные данные стремятся к определенному или предельному значению. Асимптотический анализ помогает проанализировать изменение производительности алгоритма в зависимости от размера входных данных.
Что такое нотация Big O в структуре данных?
Нотация Big O в структуре данных используется для выражения сложности алгоритмов с помощью алгебраических терминов. Она описывает верхнюю границу времени выполнения алгоритма и рассчитывает время и объем памяти, необходимые для выполнения алгоритма для входного значения.
Математическое определение
Рассмотрим функции f(n) и g(n), где функции f и g определены на неограниченном множестве положительных действительных чисел. g(n) строго положительна для каждого большого значения n.
The function f is said to be O(g) (read as big- oh of g), if, for a constant c>0 and a natural number n0, f (n) ≤ CG(n) for all n >= n0
Это можно записать как:
f(n) = O(g(n)), где n стремится к бесконечности (n → ∞).
Мы можем просто записать вышеприведенное выражение в виде:
Свойства нотации Big O
Наиболее важными свойствами нотации Big O в структуре данных являются:
Постоянное умножение:
If f(n) = CG(n), then O(f(n)) = O(g(n)) for a constant c > 0
Функция суммирования:
Если f(n) = f1(n) + f2(n) + — + FM(n) и fi(n)≤ fi+1(n) ∀ i=1, 2, –, m,
тогда O(f(n)) = O(max(f1(n), f2(n), –, fm(n))).
Логарифмическая функция:
Если f(n) = log an и g(n)=log bn, то
Полиномиальная функция:
Если f(n) = a0 + a1.n + a2.n2 + — + am.nm, то
БЕСПЛАТНЫЙ сертификационный курс по машинному обучению
Как в нотации Big O проводится анализ алгоритма во время выполнения?
Для того чтобы проанализировать и рассчитать производительность алгоритма, мы должны рассчитать и сравнить наихудшие сложности времени выполнения алгоритма. Порядок O(1) – известный как постоянное время выполнения – является самым быстрым временем выполнения алгоритма, при этом время, затрачиваемое алгоритмом, одинаково для различных размеров входных данных. Хотя постоянное время работы является идеальным временем работы алгоритма, оно достигается редко, поскольку время работы зависит от размера вводимого n.
Например, анализ времени работы алгоритма для размера n = 20:
20! = 2.432902 + 1818
- Сложность выполнения некоторых распространенных алгоритмических примеров:
- Сложность выполнения для линейного поиска – O(n)
- Сложность выполнения для двоичного поиска – O(log n)
- Сложность выполнения для пузырьковой сортировки, сортировки вставками, сортировки выбором, сортировки ведра – O(n^c).
- Сложность выполнения для экспоненциальных алгоритмов, таких как Tower of Hanoi – O(c^n).
- Сложность выполнения для Heap Sort, Merge Sort – O(n log n).
Как в нотации Big O анализируется сложность пространства?
Также важно определить пространственную сложность алгоритма. Это связано с тем, что пространственная сложность показывает, сколько места в памяти занимает алгоритм. Мы сравниваем наихудшую пространственную сложность алгоритма.
Прежде чем анализировать пространственную сложность в нотации Big O, необходимо решить следующие задачи:
- Реализация программы для конкретного алгоритма.
- Размер входных данных n должен быть известен, чтобы вычислить, сколько памяти займет каждый элемент.
Пространственная сложность некоторых распространенных алгоритмов:
Линейный поиск, двоичный поиск, пузырьковая сортировка, сортировка выбором, сортировка кучей, сортировка вставкой – пространственная сложность равна O(1).
- Радиксная сортировка – пространственная сложность составляет O(n+k).
- Быстрая сортировка – сложность пространства O(n).
- Слияние сортировок – сложность пространства O(log n).
Пример использования нотации Big O в C
Реализация алгоритма Selection Sort на языке C для нахождения наихудшей сложности алгоритма (нотация Big O):
int temp = array[i];
Пояснение:
Диапазон первого (внешнего) цикла for равен i.
Диапазон второго (внутреннего) цикла for – j.
Средняя эффективность вычисляется как n/2 для константы c, но мы игнорируем константу. Таким образом, порядок получается O(n).
Мы получаем сложность времени выполнения путем умножения порядка внутреннего и внешнего циклов. Она равна O(n^2).
Таким образом, вы можете реализовать другие алгоритмы на языке C, проанализировать и определить их сложность.
Бесплатный курс: Алгоритмы машинного обучения
Наши ученики также спрашивают
1. Что такое нотация Big O? Приведите несколько примеров.
В информатике нотация Big O является фундаментальным инструментом, используемым для определения временной сложности алгоритмов. Нотация Big O позволяет программистам классифицировать алгоритмы в зависимости от того, как изменяется время их выполнения или требования к пространству при изменении размера входных данных.
- Сложность выполнения для линейного поиска – O(n)
- Сложность выполнения для двоичного поиска – O(log n)
- Сложность выполнения для пузырьковой сортировки, сортировки выбором, сортировки вставкой, сортировки ведром – O(n^c).
- Сложность выполнения для экспоненциальных алгоритмов, таких как Tower of Hanoi – O(c^n).
- Сложность выполнения для Heap Sort, Merge Sort – O(n log n).
2. Почему используется нотация Big O?
Нотация Big O дает верхнюю границу времени выполнения или наихудшую сложность алгоритма. Она анализирует и классифицирует алгоритмы в зависимости от их времени выполнения или требований к пространству.
3. Что такое временная сложность и нотация Big O?
Временная сложность – это количество времени, которое требуется алгоритму для выполнения, когда входные данные стремятся к определенному или предельному значению. Она рассчитывает время, необходимое для выполнения каждого оператора кода в алгоритме.
Нотация Big O – это инструмент, используемый для описания временной сложности алгоритмов. Она рассчитывает время, необходимое для выполнения алгоритма при увеличении входных данных. Другими словами, вычисляется наихудшая временная сложность алгоритма.
Нотация Big O в структуре данных описывает верхнюю границу времени выполнения алгоритма. Она рассчитывает время и объем памяти, необходимые для выполнения алгоритма для входного значения.
4. Как по-другому называется нотация Big O?
Нотация Big O – это математическая нотация, названная в честь термина “порядок функции”, означающего рост функций. Она также называется символом Ландау и относится к группе асимптотических обозначений.
5. Каковы правила использования нотации Big O?
Основные правила использования нотации Big O в структуре данных следующие:
- Рассмотрим функции f(n) и g(n), где обе функции f и g определены на неограниченном множестве положительных действительных чисел. g(n) строго положительна для каждого большого значения n.
The function f is said to be O(g) (read as big- oh of g), if, for a constant c>0 and a natural number n0, f (n) ≤ CG(n) for all n >= n0
Это можно записать как:
f(n) = O(g(n)), где n стремится к бесконечности (n → ∞).
Мы можем просто записать вышеприведенное выражение в виде:
Общая производительность алгоритма равна f(n) = O(g(n) + f(n)).
- Постоянное умножение:
If f(n) = CG(n), then O(f(n)) = O(g(n)) for a constant c > 0
- Функция суммирования:
Если f(n) = f1(n) + f2(n) + — + FM(n) и fi(n)≤ fi+1(n) ∀ i=1, 2, –, m,
тогда O(f(n)) = O(max(f1(n), f2(n), –, fm(n))).
- Логарифмическая функция:
Если f(n) = log an и g(n)=log bn, то
- Полиномиальная функция:
Если f(n) = a0 + a1.n + a2.n2 + — + am.nm, то
Стремитесь к успешной карьере в области искусственного интеллекта и машинного обучения. Запишитесь на нашу программу профессиональных сертификатов по ИИ и МЛ в сотрудничестве с Университетом Пердью прямо сейчас.
Заключение
Если вы работаете с большими данными, Big O Notation особенно полезна при анализе алгоритмов. Этот инструмент помогает программистам рассчитать масштабируемость алгоритма или подсчитать, сколько шагов он должен выполнить, чтобы получить результат на основе данных, над которыми работает программа. Если вы хотите доработать свой код для повышения эффективности, нотация Big O в структуре данных может быть очень эффективной. Для получения более подробной информации о нотации Big O или кодировании начните наш сертификационный учебный курс по машинному обучению AI и будьте готовы к работе.
Найдите наш профессиональный сертификационный курс по ИИ и машинному обучению в лучших городах:
| Имя | Дата | Место | |
|---|---|---|---|
| Профессиональная сертификационная программа по ИИ и машинному обучению | Когорта начинается 7 декабря 2022 года, партия выходного дня | Ваш город | Посмотреть детали |
| Профессиональная сертификационная программа по ИИ и машинному обучению | Когорта начинается 14 декабря 2022 года, группа выходного дня | Ваш город | Посмотреть детали |
Об авторе
Simplilearn
Simplilearn является одним из ведущих мировых поставщиков онлайн-обучения по цифровому маркетингу, облачным вычислениям, управлению проектами, науке о данных, информационным технологиям, разработке программного обеспечения и многим другим развивающимся технологиям.
Рекомендуемые программы
Программа профессиональных сертификатов по искусственному интеллекту и машинному обучению
Инженер по искусственному интеллекту
Курс машинного обучения
*Пожизненный доступ к высококачественному контенту электронного обучения с самообучением.
Следующая статья
Насколько велики большие данные? Виды больших данных
Рекомендуемые ресурсы
Руководство по карьере в области больших данных: Всеобъемлющее руководство, как стать инженером по большим данным