Нотация Big O (иногда называемая Big Omega) — один из самых фундаментальных инструментов для программистов для анализа временной и пространственной сложности алгоритма. Обозначение Big O — это асимптотическое обозначение для измерения верхней границы производительности алгоритма.
Ваш выбор алгоритма и структуры данных имеет значение, когда вы пишете программное обеспечение со строгими SLA или большими программами. Нотация Big O позволяет сравнивать производительность алгоритмов, чтобы найти лучшее для вашей ситуации. Рейтинг Big O помогает сократить время бега по сравнению с конкурентами.
Эта статья призвана дать быстрые ответы на распространенные вопросы о нотации Big O, которые могут возникнуть у вас или с которыми вы можете столкнуться во время интервью.
Давайте начнем!
Что такое Big-O Notation?
Big-O Notation — это математическая функция, используемая в информатике для описания сложности алгоритма. Обычно это мера времени выполнения, необходимого для выполнения алгоритма.
Но вместо того, чтобы сообщать вам, насколько быстро или медленно выполняется алгоритм, он сообщает вам, как производительность алгоритма изменяется в зависимости от размера ввода (размера n).
Наибольшие факторы, влияющие на Big O, — это количество шагов и количество итераций, которые программа выполняет для повторяющихся структур, таких как forцикл.
Для нашего формального определения мы определяем O(g(n)) как набор функций и функция f(n) может быть членом этого набора, если он удовлетворяет следующим условиям:
≤ ≤ cg(n)0 ≤ ≤
Константа cявляется положительной константой, и неравенство сохраняется после того, как размер ввода nпересекает положительный порогn0п 0
Если алгоритм выполняет вычисление для каждого элемента в массиве размера n, мы можем сказать, что алгоритм работает в O(n) время (или имеет постоянную временную сложность) и выполняет О( 1 ) работать по каждому пункту.
Что такое сложность пространства и сложность времени?
Временная сложность алгоритма определяет количество времени, затрачиваемого алгоритмом на выполнение, в зависимости от длины входных данных. Точно так же пространственная сложность алгоритма количественно определяет объем пространства или памяти, занимаемой алгоритмом для работы, в зависимости от длины входных данных.
Оба зависят от нескольких внешних факторов, таких как компьютерное оборудование, операционная система и т. Д., Но ни один из этих факторов не учитывается при анализе алгоритма.
Вот некоторые общие сложности, с которыми вы столкнетесь с алгоритмами:
- Quadratic time: O(n^2)
- Linear time: O(n)O(n)
- Logarithmic time: O(n log n)
- Exponential time: 2 ^{polyn}
- Factorial time: O(n!)
- Polynomial time: 2^2O(logn)
Big-O Notation для структур данных
| Data Structure | Insert | Retrieve |
|---|---|---|
| Array | O(1) | O(1) |
| Linked List | At Head: O(1) At Tail: O(n) | O(n) |
| Binary Search | O(n) | O(n) |
| Dynamic Array | O(1) | O(1) |
| Stack | O(1) | O(1) |
| Hash Table | O(n) | O(n) |
Big-O Notation для алгоритмов сортировки
| Sorting Algorithm | Worst-case scenario | Average Case | Best-case scenario |
|---|---|---|---|
| Bubble Sort | O(n^2) | O(n^2) | O(n) |
| Insertion Sort | O(n^2) | O(n^2) | O(n) |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) |
| Quick Sort | O(n^2) | O(n log n) | O(n log n) |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) |
| Heap sort | O(n log n) | O(n log n) | O(n log n) |
Примечание: даже если производительность быстрой сортировки в наихудшем случае является квадратичной (O (n2)), но на практике для сортировки часто используется быстрая сортировка, поскольку ее средний регистр является логарифмическим (O(n log n)).
Подведение итогов и следующие шаги
Теперь, когда вы разобрались с общими темами в Big O, вы должны быть соответствующим образом подготовлены к ответу на большинство вопросов, с которыми вы сталкиваетесь. Есть и другие более технические темы, которые мы не затронули, например,
- Complexity Theory
- Big Theta notation
- Lower Bounds Analysis
- Probabilistic Analysis
- Amortized Analysis
- Recursion
