Шпаргалка по Big O

Бесплатно

Удобный для поиска и печати справочник по нотации Big O: временная и пространственная сложность для массивов, хеш-таблиц, деревьев, куч, графов, сортировки и поиска. Бесплатно.

Complexity classes

O(1): constant

Same cost regardless of input size

O(log n): logarithmic

Halves the problem each step

O(n): linear

Touches every element once

O(n log n): linearithmic

Best possible comparison sort

O(n²): quadratic

Every pair: nested loops over input

O(n³): cubic

Triple nesting, e.g. naive matrix multiply

O(2^n): exponential

Doubles per element: all subsets

O(n!): factorial

All orderings: brute-force permutations

n = 10^6: O(n log n) ≈ 2×10^7 ops

Fine: well under a second

n = 10^6: O(n²) = 10^12 ops

Too slow: think minutes to hours

Rule: drop constants and lower terms

O(3n² + 5n) is just O(n²)

Amortized O(1)

Occasionally slow, cheap on average

Arrays & dynamic arrays

Access by index: O(1)

Direct address arithmetic

Search (unsorted): O(n)

Must scan every element

Search (sorted): O(log n)

Binary search on sorted data

Append (dynamic): O(1) amortized

Occasional resize copies all

Insert at front/middle: O(n)

Shifts all later elements

Delete at end: O(1)

No shifting required

Delete at front/middle: O(n)

Shifts elements to close the gap

Resize (grow ×2): O(n)

Copy into a bigger buffer

Slice/copy: O(k)

Proportional to slice length

Space: O(n)

May hold up to 2× capacity slack

Cache-friendly: contiguous memory

Real-world edge over linked lists

Linked lists

Access by index: O(n)

Must walk from the head

Search: O(n)

Linear scan, no shortcuts

Insert/delete at head: O(1)

Repoint the head pointer

Insert/delete at tail: O(1) with tail ptr

O(n) without one (singly)

Insert after known node: O(1)

The big win over arrays

Delete known node (doubly): O(1)

Prev pointer makes unlink cheap

Delete known node (singly): O(n)

Must find the predecessor

Reverse: O(n) time, O(1) space

Classic pointer-flip interview task

Detect cycle: O(n), O(1) space

Floyd's tortoise and hare

Space: O(n) plus pointer overhead

1–2 pointers per node

Stacks & queues

Stack push/pop/peek: O(1)

LIFO: last in, first out

Stack search: O(n)

No random access

Queue enqueue/dequeue: O(1)

FIFO: first in, first out

Deque push/pop both ends: O(1)

Double-ended queue

Queue via 2 stacks: O(1) amortized

Classic interview construction

Min-stack: O(1) getMin

Track min alongside each push

Monotonic stack: O(n) total

Next greater element problems

Stack use: DFS, undo, call stack

Recursion is an implicit stack

Queue use: BFS, schedulers, buffers

Level-order processing

Space: O(n)

One slot per stored element

Hash tables

Insert: O(1) avg, O(n) worst

Worst = all keys collide

Lookup: O(1) avg, O(n) worst

Hash, then probe the bucket

Delete: O(1) avg, O(n) worst

Same story as lookup

Resize/rehash: O(n)

Triggered past the load factor

Load factor ~0.7

Typical resize threshold

Chaining

Collisions become linked lists

Open addressing

Probe for the next free slot

Ordered iteration: not provided

Use a tree map if order matters

Hash set membership: O(1) avg

The go-to de-dupe structure

Space: O(n)

Plus empty buckets overhead

Pattern: trade O(n) space for O(1) lookups

Two-sum in one pass

Binary search trees & balanced trees

BST search/insert/delete: O(h)

h = tree height

BST average: O(log n)

Random inserts stay bushy

BST worst: O(n)

Sorted inserts make a chain

AVL all ops: O(log n) guaranteed

Strict balance, fast lookups

Red-black all ops: O(log n)

Looser balance, faster writes

B-tree all ops: O(log n)

Wide nodes: databases, disks

In-order traversal: O(n)

Visits keys in sorted order

Min/max: O(log n) balanced

Walk far left / far right

Successor/predecessor: O(log n)

Ordered neighbors of a key

Range query: O(log n + k)

k = number of results

Trie lookup: O(L)

L = key length, not item count

Space: O(n)

2–3 pointers per node

Heaps

Peek min/max: O(1)

Root holds the extreme

Insert: O(log n)

Bubble up to restore order

Extract min/max: O(log n)

Pop root, sift down

Build heap from array: O(n)

Heapify beats n inserts

Search arbitrary key: O(n)

Heaps are not for lookups

Decrease-key: O(log n)

Core of Dijkstra's algorithm

Top-k of n items: O(n log k)

Keep a size-k heap

Two heaps: O(log n) per insert

Running median pattern

Stored as an array

Children at 2i+1, 2i+2

Space: O(n)

No pointers needed

Graphs

Adjacency list space: O(V + E)

Best for sparse graphs

Adjacency matrix space: O(V²)

Best for dense graphs

Edge check: list O(deg), matrix O(1)

The core trade-off

Iterate neighbors: list O(deg), matrix O(V)

Lists win for traversal

BFS / DFS: O(V + E)

With an adjacency list

Topological sort: O(V + E)

DAG ordering (Kahn / DFS)

Dijkstra: O((V + E) log V)

Binary heap, no negative edges

Bellman-Ford: O(V·E)

Handles negative edges

Floyd-Warshall: O(V³)

All-pairs shortest paths

Prim / Kruskal MST: O(E log V)

Minimum spanning tree

Union-Find: O(α(n)) ≈ O(1)

With rank + path compression

A*: O(E) best case

Heuristic-guided Dijkstra

Sorting algorithms

Bubble sort: O(n²), best O(n)

O(1) space; only teaching value

Insertion sort: O(n²), best O(n)

O(1) space; great when nearly sorted

Selection sort: O(n²) always

O(1) space; fewest swaps

Merge sort: O(n log n) always

O(n) space; stable; predictable

Quick sort: avg O(n log n), worst O(n²)

O(log n) space; fastest in practice

Heap sort: O(n log n) always

O(1) space; not stable

Tim sort: O(n log n), best O(n)

Python/Java built-in; stable

Counting sort: O(n + k)

k = value range; not comparison

Radix sort: O(d·(n + k))

d = digits; ints and strings

Bucket sort: avg O(n + k), worst O(n²)

Uniformly distributed input

Shell sort: ~O(n^1.3)

Gap-based insertion sort

Comparison-sort lower bound: Ω(n log n)

Cannot do better by comparing

Stable: merge, insertion, tim, counting

Equal keys keep their order

Searching algorithms

Linear search: O(n)

Only option for unsorted data

Binary search: O(log n)

Sorted arrays only

Binary search space: O(1) iterative

O(log n) if recursive

Hash lookup: O(1) avg

Fastest membership test

BST search: O(log n) balanced

Also gives sorted neighbors

Trie prefix search: O(L)

Autocomplete workhorse

BFS shortest path (unweighted): O(V + E)

First hit is the shortest

lower_bound / bisect: O(log n)

First element >= target

Quickselect (k-th element): avg O(n)

Worst O(n²); no full sort

Ternary search: O(log n)

Peak of a unimodal function

Interpolation search: avg O(log log n)

Uniform sorted data only

Common patterns

Two pointers: O(n)

Pair sums in a sorted array

Sliding window: O(n)

Best subarray of size/condition k

Fast & slow pointers: O(n)

Cycle detection, list middle

Prefix sums: O(n) build, O(1) query

Range-sum questions

Binary search on answer: O(n log range)

"Min capacity to ship in D days"

Monotonic stack: O(n)

Next greater / histogram area

Backtracking: O(2^n) or O(n!)

Subsets / permutations search

Memoized DP: states × transition cost

Kills exponential recursion

Greedy: usually O(n log n)

Sort, then one linear pass

Divide & conquer: T(n) = 2T(n/2) + O(n)

Master theorem: O(n log n)

Bit manipulation: O(1) per op

Sets of <=64 items in an int

Meet in the middle: O(2^(n/2))

Halves an exponential search

Space complexity notes

In-place: O(1) extra space

Quick sort, heap sort, reversal

Recursion costs stack space

Depth d means O(d) memory

DFS space: O(h) / O(V) worst

h = depth of recursion

BFS space: O(w)

w = widest level (can be n/2)

Merge sort: O(n) auxiliary

The price of stability

Memoization: O(#states)

Time saved, memory spent

DP table row trick: O(n²) → O(n)

Keep only the previous row

Hash-based de-dupe: O(n) space

vs O(1) sort-first approach

Tail recursion: O(1) if optimized

Not guaranteed in every language

Streaming: O(1) or O(k) space

One pass, constant memory

Always state time AND space

Interviews expect both

Нет записей, соответствующих «:q».

О Шпаргалка по Big O

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

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

Шпаргалка бесплатна и работает на стороне клиента: фильтруйте строки на лету через поле поиска, переходите между разделами с помощью закреплённого оглавления, копируйте любую запись одним щелчком и печатайте страницу как справку для рабочего стола.

Как использовать Шпаргалка по Big O

Откройте шпаргалку и начните с классов сложности, чтобы закрепить O(1), O(log n), O(n), O(n log n) и O(n²).
Найдите структуру или алгоритм, например hash table, quicksort или BFS, чтобы отфильтровать все строки на лету.
Сравнивайте разделы о структурах данных, когда выбираете между списком, мапой и деревом.
Нажмите на запись или значок копирования, чтобы скопировать её в буфер обмена.
Распечатайте шпаргалку как офлайн-справочник по сложности.

Часто задаваемые вопросы

Двенадцать разделов: классы сложности, массивы и динамические массивы, связные списки, стеки и очереди, хеш-таблицы, двоичные деревья поиска и сбалансированные деревья, кучи, графы, алгоритмы сортировки, алгоритмы поиска, распространённые шаблоны и заметки о пространственной сложности.

Да. Там, где они различаются (поиск в хеш-таблице, quicksort, несбалансированный BST), в строке указаны оба, так что видна стоимость при неблагоприятных данных.

Она создана именно для этого: разделы сортировки и поиска плюс раздел распространённых шаблонов охватывают сложности, которые интервьюеры просят назвать вслух.

Да. Затраты памяти показаны рядом с затратами времени, а заключительный раздел охватывает глубину стека рекурсии, различие между памятью на месте и вспомогательной памятью и обычные компромиссы.

Да, полностью бесплатен: с поиском, печатью и отображением в браузере без регистрации.

Шпаргалка по Big O

Complexity classes

Arrays & dynamic arrays

Linked lists

Stacks & queues

Hash tables

Binary search trees & balanced trees

Heaps

Graphs

Sorting algorithms

Searching algorithms

Common patterns

Space complexity notes

О Шпаргалка по Big O

Как использовать Шпаргалка по Big O

Часто задаваемые вопросы

Что охватывает шпаргалка по Big-O?

Показывает ли она средний и худший случаи?

Полезна ли она для собеседований по программированию?

Охватывает ли она и пространственную сложность?

Бесплатен ли справочник по Big-O?

Похожие инструменты

Популярные запросы

Встроить этот инструмент