Name: Password: Sign in
Data Structures and Algorithm Analysis Notes 中的文章
  • [Lecture 1] Introduction, Mathematics Review, Recursion
  • [Lecture 2] Asymptotic Notation, Algorithm Analysis
  • 本文在 署名-非商业性使用-相同方式共享 3.0 版权协议下发布, 转载请注明出自 kyleslight.net

    [Lecture 2] Asymptotic Notation, Algorithm Analysis

    1. Asymptotic Notation

    1.1 Definitions

    Here are some definitions to demonstrate the value trend of a function when the input N grows up .

    The big-O notation O defines a class of functions that have the same attribution :

    T(N)=O(f(N)) if there are positive constants c and n0 such that T(N)cf(N) when Nn0.

    Note that 「=」 here is not a tradition symbol 「equal」, which describes T(N) belongs to a set of functions satisfied with the requirement above.

    Big-O Notation
    Big-O notation

    O(f(N)) guarantees the function T(N) has upper bound in the long run. We will not mind what the constant items c and n0 would be when N becomes a huge number, that’s a fundamental idea about the term 「asymptotic」, T(N) will be under some restriction of f(N) in the end, when we say some function is of O(f(N)), we guarantee the growth rate of this function will not be greater than f(N).

    Almost the same thing happens with the big-omega notation Ω :

    T(N)=Ω(f(N)) if there are positive constants c and n0 such that T(N)cf(N) when Nn0

    Big-Omega Notation
    Big-Omega Notation

    To make it more exactly, there is big-theta notation Θ to control the upper bound and lower bound :

    T(N)=Θ(f(N)) if and only if T(N)=O(f(N)) and T(N)=Ω(f(N))

    And there is little-o notation describing the strict relation case, in which T(N) is not in the set of Θ(f(N)) :

    T(N)=o(f(N)) if T(N)=O(f(N)) and T(N)Θ(N)

    As we will see those notations in our future, they are efficient tools to compare the relative growth rate of functions. Thus we will introduce some important rules firstly.

    1.2 Rules of Asymptotic Notations

    Rule 1

    Supposing that

    T1(N)=O(f(N)),T2(N)=O(g(N))

    we have :

    T1(N)+T2(N)=O(f(N))+O(g(N))=O(max(f(N),g(N)))

    T1(N)T2(N)=O(f(N)g(N))

    Rule 2

    If T(N) is a polynomial of degree k, then T(N)=Θ(Nk)

    Rule 3

    logkN=O(N), for any constant k, that means the logarithmic functions grow more slowly than any polynomial functions

    And we can make a list of functions in the order of growth rate :

    Function Name
    c Constant
    logN Logarithmic
    log2N Log-squared
    N Linear
    NlogN
    N2 Quadratic
    N3 Cubic
    2N Exponential

    This list can be helpful to get intuitive impression. Besides we can compare the growth rate of two functions in a more general way by computing the limit :

    limNf(N)g(N)

    The value of the limit shows the relationship of two functions :

    • The limit is 0 : f(N)=o(g(N))
    • The limit is c0 : f(N)=Θ(g(N))
    • The limit is : g(N)=o(f(N))
    • No limit : No relationship of two functions

    Here’s a brief example, supposing we have f(N)=NlogN and g(N)=N1.5 :

    limNf(N)g(N)=limNNlogNN1.5

    Using L’Hôpital’s rule, we have :

    limNf(N)g(N)=limNlogN+const11.5N0.5

    According to Rule 1 :

    limNf(N)g(N)=limNlogN1.5N0.5+limNconst1N0.5

    Using L’Hôpital’s rule again :

    limNf(N)g(N)=limNconst2N0.5+limNconst1N0.5

    limNf(N)g(N)=0+0=0

    In fact this is another example to show logN is slower than any power function Na when a is positive.

    2. Algorithm Analysis

    2.1 Model and Running Time

    Take a piece of code, and we would like to know how well it would performance, the typical idea is to measure the running time. However there are lots of factors that will have effects on time, such as compiler options, the clock frequency of this machine you use, etc. We want our program analysis to be independent with those non-program factors.

    In order to realise independence, we use a model assuming the basic operations, such as addition, multiplication, comparison, and assignment run for a time unit. Though we know exactly loading data from memory is much slower than executing addition in CPU. In addition we also assume our memory is infinity.

    Since the input scale can be changeable, we will use Tworst in worst-case to guarantee the upper bound of running time, and Tavg in average-case to represent typical behaviour.

    ( Note that Tavg sometimes would be really hard to analysis, in other case, the definition about average will have affect on Tavg. )

    Now we will introduce the methods for algorithm analysis thought a simple problem.

    Copyright (c) 2014-2016 Kyles Light.
    Powered by Tornado.
    鄂 ICP 备 15003296 号