分析时间复杂度&空间复杂度,以二分查找和斐波那契数的递归和非递归算法为例

一、时间复杂度:实际是指程序运行次数,而不是程序运行时间

1.我们一般讨论的是最坏时间复杂度,这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上限,以最坏代表最全。

2.时间复杂度的书写规则:

忽略常数项,用O(1)表示
选取最坏时间复杂度即选取增长最快的项
递归的时间复杂度=递归总次数 * 每次递归中基本操作所执行的次数

例1,代码如下:

void Test2(int n)
{
    int iCount = 0;
    for (int iIdx = 0; iIdx < 10; ++iIdx)
    {
        iCount++;
    }
    for (int iIdx = 0; iIdx < 2*n; ++iIdx)
    {
        iCount++;
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            iCount++;
        }
    }
}

f(n)=n^2+2n+10
则O(n)=n^2 //规则①②

例2,代码如下:

int factorial(int n)//求n的阶乘,递归法
{
    if(n<=1)
    return 1;
    else
    {
        return n*factorial(n-1);
    }
}

因为if()判断的两种情况对应的两个代码块中的基本操作的执行次数都为1
递归次数为n,所以O(n)=n*1=n //规则③

例3,代码如下:

void Test4(int m, int n)// f(n,m) = 2*m*n == O(m*n)
{
    int iCount = 0;
    for (int i = 0; i < 2*m ; ++i)
    {
        for (int j = 0; j < n ; ++j)
        {
        iCount++;
        }
    }
}

f(n)=2*m*n
则O(n)=(m*n) //规则①

3 . 常用的时间复杂度有以下七种,算法时间复杂度依次增加:

O(1):常数型
O(log2 n):对数型
O(n):线性型
O(nlog2n):二维型
O(n^2):平方型
O(n^3):立方型
O(2^n):指数型

二、空间复杂度:不是计算实际占用的空间,而是计算整个算法的辅助空间单元的个数,与问题的规模没有关系(简单理解就是算法执行时创建的变量(包括临时变量)个数)

1.空间复杂度书写规则:

忽略常数,用O(1)表示
递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间
对于单线程来说,递归有运行时堆栈,求的是递归最深的那一次压栈所耗费的空间的个数,因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。递归是要返回上一层的,所以它所需要的空间不是一直累加起来的
(简单说明单线程和多线程的区别:当你吃饭的时候电话响了,你接完电话再吃饭,这是单线程;你边吃饭边接电话,这是多线程。)

例1,代码如下:

int Sum(int N)
{
    int count = 0;
    for(int i = 1; i <= N; ++i)
    {   
        count += i;
    }
    return count;
}

空间复杂度:O(n)=1 //规则①

例2,代码如下:

void fun(int n)
{
    int arr[10];
    if(n<0)
    {
        return 1;
    }
    else
    {
        return fun(n-1);
    }
}

每次调用fun函数就会创建一个10个元素的整型数组,调用次数为n
空间复杂度:O(n*10)=O(n) //规则①②

三、实例解析:
1.二分查找
1>递归法:

int binary_search_recursion(int *arr,int left,int right,int num)
{
    assert(arr);

    if(left<=right)
    {
        int mid = left + ((right - left) >> 1);
        if (arr[mid] > num)
        {
            return binary_search_recursion(arr,left,mid-1,num);
        }
        else if (arr[mid] < num)
        {
            return binary_search_recursion(arr, mid+1, right, num);
        }
        else
        {
            return mid;
        }
    }
    else
    {
        return -1;
    }
}

《分析时间复杂度&空间复杂度,以二分查找和斐波那契数的递归和非递归算法为例》

递归的次数和深度都是log2 n,每次所需要的辅助空间都是常数级别的:
时间复杂度 : O(log2 n)
空间复杂度:O(log2 n)

2>迭代法:

int binary_sreach_iteration(int *arr, int sz, int num)
{
    int mid = 0;
    int left = 0;
    int right = sz - 1;

    while (left<=right)
    {
        mid = (left + right)>>1;
        if (arr[mid]>num)
        {
            right = mid - 1;
        }
        else if (arr[mid]<num)
        {
            left = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

循环的基本次数是log2 n,所以:时间复杂度是O(log2 n);
由于辅助空间是常数级别的所以:空间复杂度是O(1);

2.斐波那契
1>递归法:

int fib_recursion(int n)
{
    if (n <= 2)
        return 1;
    else
    {
        return fib(n - 1) + fib(n - 2);
    }
}

《分析时间复杂度&空间复杂度,以二分查找和斐波那契数的递归和非递归算法为例》

循环的基本操作次数是n-1,辅助空间是n+1,所以:
时间复杂度O(2^n)
空间复杂度O(n)

2>迭代法:

int fib_iteration(int n)
{
    int a = 1;
    int b = 1;
    int c = 1;
    if (n<2)
    {
        return n;
    }
    while (n>2)
    {
        c = a + b;
        a = b;
        b = c;
        n--;
    }
    return c;
}

循环的基本次数是n-1,所用的辅助空间是常数级别的:
时间复杂度:O(n)
空间复杂度:O(1)

    原文作者:王老桔
    原文地址: https://blog.csdn.net/w_y_x_y/article/details/78733667
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞