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.

    O(f(N