Συνοπτικός οδηγός Big-O

Δωρεάν

Μια αναζητήσιμη, εκτυπώσιμη αναφορά Big-O: πολυπλοκότητα χρόνου και χώρου για arrays, hash tables, δέντρα, σωρούς, γράφους, ταξινόμηση και αναζήτηση. Δωρεάν.

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

Αυτό το cheat sheet Big-O βάζει την αλγοριθμική πολυπλοκότητα σε μία αναζητήσιμη σελίδα: τις ίδιες τις κλάσεις πολυπλοκότητας, μετά το κόστος χρόνου και χώρου για arrays και δυναμικά arrays, συνδεδεμένες λίστες, στοίβες και ουρές, hash tables, δυαδικά δέντρα αναζήτησης και ισορροπημένα δέντρα, σωρούς (heaps), γράφους, αλγορίθμους ταξινόμησης, αλγορίθμους αναζήτησης, κοινά μοτίβα, και σημειώσεις πολυπλοκότητας χώρου.

Είναι η αναφορά τόσο για την επιλογή δομής δεδομένων όσο και για προετοιμασία συνέντευξης: η μέση και χειρότερη περίπτωση για μια αναζήτηση hash table, γιατί ένα ισορροπημένο δέντρο ξεπερνά ένα απλό BST, ποιες ταξινομήσεις είναι σταθερές και ποιες in place, και τι κοστίζουν τα μοτίβα two-pointer, sliding-window και memoization.

Το φύλλο είναι δωρεάν και λειτουργεί στην πλευρά του πελάτη: φιλτράρετε γραμμές ζωντανά με το πλαίσιο αναζήτησης, μετακινηθείτε μεταξύ ενοτήτων με τον σταθερό πίνακα περιεχομένων, αντιγράψτε οποιαδήποτε εγγραφή με ένα κλικ και εκτυπώστε τη σελίδα ως αναφορά γραφείου.

Πώς να χρησιμοποιήσετε το Συνοπτικός οδηγός Big-O

Ανοίξτε το φύλλο και ξεκινήστε με τις Κλάσεις πολυπλοκότητας για να αγκυρώσετε τα O(1), O(log n), O(n), O(n log n) και O(n²).
Αναζητήστε μια δομή ή αλγόριθμο όπως hash table, quicksort ή BFS για να φιλτράρετε κάθε γραμμή ζωντανά.
Συγκρίνετε τις ενότητες δομών δεδομένων όταν επιλέγετε ανάμεσα σε μια λίστα, ένα map και ένα δέντρο.
Κάντε κλικ σε μια εγγραφή ή στο εικονίδιο αντιγραφής της για να την αντιγράψετε στο πρόχειρό σας.
Εκτυπώστε το φύλλο για offline αναφορά πολυπλοκότητας.

Συχνές ερωτήσεις

Δώδεκα ενότητες: κλάσεις πολυπλοκότητας, arrays και δυναμικά arrays, συνδεδεμένες λίστες, στοίβες και ουρές, hash tables, δυαδική αναζήτηση και ισορροπημένα δέντρα, σωρούς, γράφους, αλγορίθμους ταξινόμησης, αλγορίθμους αναζήτησης, κοινά μοτίβα, και σημειώσεις πολυπλοκότητας χώρου.

Ναι. Όπου διαφέρουν (αναζητήσεις hash table, quicksort, ένα μη ισορροπημένο BST) η γραμμή αναφέρει και τις δύο, ώστε να δείτε το κόστος όταν τα δεδομένα είναι δυσμενή.

Είναι φτιαγμένο ακριβώς για αυτό: οι ενότητες ταξινόμησης και αναζήτησης συν η ενότητα κοινών μοτίβων καλύπτουν τις πολυπλοκότητες που οι ερευνητές σας ζητούν να πείτε δυνατά.

Ναι. Τα κόστη χώρου εμφανίζονται μαζί με τα κόστη χρόνου, και μια τελική ενότητα καλύπτει το βάθος στοίβας αναδρομής, in-place έναντι βοηθητικού χώρου και τους συνήθεις συμβιβασμούς.

Ναι, εντελώς δωρεάν: αναζητήσιμη, εκτυπώσιμη και αποδίδεται στο πρόγραμμα περιήγησής σας χωρίς εγγραφή.

Δημοφιλείς αναζητήσεις

big o cheat sheet time complexity chart data structure complexity sorting algorithm complexity big o notation table space complexity chart algorithm complexity reference

Χρειάζεστε βοήθεια;

Βρήκατε πρόβλημα με αυτό το εργαλείο; Ενημερώστε μας.

Αναφορά προβλήματος

Προσθέστε αυτό το δωρεάν εργαλείο στον δικό σας ιστότοπο: αντιγράψτε και επικολλήστε τον παρακάτω κώδικα.

<iframe src="https://tweakee.com/el/tools/developer/big-o-cheatsheet?embed=1" width="100%" height="720" style="border:1px solid #e2e8f0;border-radius:12px;max-width:680px;" loading="lazy"></iframe>

Συνοπτικός οδηγός 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

Συχνές ερωτήσεις

Τι καλύπτει το cheat sheet Big-O;

Δείχνει τη μέση και τη χειρότερη περίπτωση;

Είναι χρήσιμο για συνεντεύξεις προγραμματισμού;

Καλύπτει και την πολυπλοκότητα χώρου;

Είναι δωρεάν η αναφορά Big-O;

Σχετικά Εργαλεία

Δημοφιλείς αναζητήσεις

Ενσωματώστε αυτό το εργαλείο