时间复杂度

cookbook上的几个特殊例子分析

Example 1

void hello (int n){
    for( int sz = 1 ; sz < n ; sz += sz)
        for( int i = 1 ; i < n ; i ++)
            cout << "Hello" << endl;
}

第一个循环的条件是”sz+=sz"，相当于递归，区间段长度为sz。

时间复杂度为：O(nlogn)

Example 2

bool isPrime (int n){
    for( int x = 2 ; x * x <= n ; x ++ )
        if( n % x == 0)
            return false;
    return true;
}

循环条件相当于x*2=n。

时间复杂度为：O(sqrt(n))

例1和例2说明，判断时间复杂度需要具体看循环条件是什么，而不能直接看循环结构。

Example 3

有一个字符串数组，将数组中的每一个字符串按照字母序排序，之后再将整个字符串数组按照字典序排序。两步操作的整体时间复杂度是多少呢？

1. 对每一个字符串排序时，一般用快排、归并等算法排。假设字符串最长为s，则该步骤的时间复杂度为：O(slogs)。

2. 对字符串组排序时，也一般用快排、归并等算法排。假设数组长度为n，则该步骤的时间复杂度为：O(nlogn)。

总的时间复杂度为：O(nslog(s+n)

空间复杂度

Example 1

int sum( int n ){
    assert( n >= 0 )
    int ret = 0;
    for ( int i = 0 ; i <= n ; i++)
        ret += i;
    return ret;
}

空间复杂度为：O(1)

Example 2

int sum( int n ){
    assert( n >= 0 )
    if ( n == 0 )
        return 0;
    return n + sum( n - 1);
}

递归调用sum函数，相当于n+n-1+n-2+n-3+....+1。

空间复杂度为：O(n)

递归的时间复杂度

主定理、递归树、假设验证法