9. Complexity

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil -- Donald Knuth

../_images/performance-optimization-knuth.jpg

9.1. Rationale

  • Podstawy optymalizacji i wydajności systemów

  • Computational Complexity (pol. złożoność obliczeniowa)

  • Memory Complexity (pol. złożoność pamięciowa)

  • Cognitive Complexity (pol. złożoność kognitywna)

  • Cyclomatic Complexity (pol. złożoność cyklometryczna)

  • Big O notation 1

  • https://wiki.python.org/moin/TimeComplexity

../_images/performance-complexity-bionotation.png

9.2. Computational Complexity

9.3. Memory Complexity

9.4. Cognitive Complexity

9.5. Cyclomatic Complexity

  • Measures the minimum number of test cases required for full test coverage.

9.6. Big O notation

Most common:

  • O(sqrt_n)

  • O(log_n)

  • O(log2_n)

  • O(1)

  • O(n)

  • O(nlog2_n)

  • O(n^2)

  • O(2^n)

  • O(n!)

Table 9.2. Table of common time complexities 1

Running time (T(n))

Name

Example algorithms

O(1)

constant time

Finding the median value in a sorted array of numbersCalculating (−1)n

O(α(n))

inverse Ackermann time

Amortized time per operation using a disjoint set

O(log* n)

iterated logarithmic time

Distributed coloring of cycles

O(log log n)

log-logarithmic

Amortized time per operation using a bounded priority queue

O(log n)

logarithmic time

Binary search

poly(log n)

polylogarithmic time

O(nc) where 0 < c < 1

fractional power

Searching in a kd-tree

O(n)

linear time

Finding the smallest or largest item in an unsorted array, Kadane's algorithm, linear search

O(n log* n)

n log-star n time

Seidel's polygon triangulation algorithm

O(n log n)

linearithmic time

Fastest possible comparison sort; Fast Fourier transform

n poly(log n)

quasilinear time

O(n2)

quadratic time

Bubble sort; Insertion sort; Direct convolution

O(n3)

cubic time

Naive multiplication of two n×n matrices. Calculating partial correlation

2O(log n) = poly(n)

polynomial time

Karmarkar's algorithm for linear programming; AKS primality test

2poly(log n)

quasi-polynomial time

Best-known O(log2 n)-approximation algorithm for the directed Steiner tree problem

O(2nε) for all ε > 0

sub-exponential time

Best-known algorithm for integer factorization; formerly-best algorithm for graph isomorphism

2o(n)

sub-exponential time

Best-known algorithm for integer factorization; formerly-best algorithm for graph isomorphism

2O(n)

exponential time (with linear exponent)

Solving the traveling salesman problem using dynamic programming

2poly(n)

exponential time

Solving matrix chain multiplication via brute-force search

O(n!)

factorial time

Solving the traveling salesman problem via brute-force search

22poly(n)

double exponential time

Deciding the truth of a given statement in Presburger arithmetic

9.7. References

1(1,2)

https://en.wikipedia.org/wiki/Big_O_notation

9.8. Further Reading