Читать книгу Data Structure and Algorithms Using C++ - Sachi Nandan Mohanty - Страница 15

The asymptotic notations are the symbols which are used to solve the different algorithms and the notations are

 Big Oh Notation (O)

 Little Oh Notation (o)

 Omega Notation (Ω)

 Theta Notation (θ)

Big Oh (O) Notation

This Notation gives the upper bound for a function to within a constant factor. We write f(n) = O(g(n)) if there are +ve constants n0 and C such that to the right of n0, the value of f(n) always lies on or below Cg(n)

Omega Notation (Ω)

This notation gives a lower bound for a function to with in a constant factor. We write f(n) = Ωg(n) if there are positive constants n0 and C such that to the right of n0 the value of f(n) always lies on or above Cg(n)

Theta Notation (θ)

This notation bounds the function to within constant factors. We say f(n) = θg(n) if there exists +ve constants n0, C1 and C2 such that to the right of n0 the value of f(n) always lies between c1g(n) and c2(g(n)) inclusive.

Little Oh Notation (o)

Introduction

An important question is: How efficient is an algorithm or piece of code? Efficiency covers lots of resources, including:

CPU (time) usage

Memory usage

Disk usage

Network usage

All are important but we will mostly talk about CPU time

Be careful to differentiate between:

Performance: how much time/memory/disk/... is actually used when a program is running. This depends on the machine, compiler, etc., as well as the code.

Complexity: how do the resource requirements of a program or algorithm scale, i.e., what happens as the size of the problem being solved gets larger. Complexity affects performance but not the other way around. The time required by a method is proportional to the number of “basic operations” that it performs. Here are some examples of basic operations:

one arithmetic operation (e.g., +, *). one assignment one test (e.g., x == 0) one read one write (of a primitive type)

Note: As an example,

O(1) refers to constant time.

O(n) indicates linear time;

O(n^k) (k fixed) refers to polynomial time;

O(log n) is called logarithmic time;

O(2ⁿ) refers to exponential time, etc.

n2 + 3n + 4 is O(n2), since n2 + 3n + 4 < 2n2 for all n > 10. Strictly speaking, 3n + 4 is O(n2), too, but big-O notation is often misused to mean equal to rather than less than.