时间复杂度和空间复杂度

时间:2021-06-04 17:06:15

时间复杂度

计算机中,算法的时间复杂度是一个函数,它定性的描述了程序的运行时间,常用大O表示。
在实际中我们通常情况考量的是算法的最坏情况。
递归算法的时间复杂度计算:递归总次数*每次递归中执行基本操作的次数。

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度,所以它强调的是使用的辅助空间的大小,而不是所有空间的大小。
要注意的是递归算法的空间复杂度,假如递归深度为N*每次递归的辅助空间大小,如果每次递归的辅助空间为常数,则空间复杂度为O(N)。

二分查找法:

int check(const int* ptr,const int x,const int len)  
{  
    int left=0;  
    int right=len-1;  
    int mid=(left+right)/2;  
    while(left<=right)  
    {  
        if(x<ptr[mid])  
        {  
            right=mid-1;  
        }  
        else if(x>ptr[mid])  
        {  
            left=mid+1;  
        }  
        else  
        {  
            return mid;  
        }  
    }  
    return -1;  
}  

通常用最坏的情况打算,用二分法找的时候,第一次在n/2的范围内找,第二次在n/4的范围内找,所以第x次就是n/2^x,x = log2^n,所以这个函数的时间复杂度为O(log2^n).
但是它这个函数所用的辅助空间是有限的,所以它的空间复杂度为O(1).

递归实现的斐波那契数:

long long fib(long long n)  
{  
    assert(n>=0);  
    return (n<2)?(n):(fib(n-1)+fib(n-2));  
}  

由递归实现的斐波那契数列可得:
时间复杂度和空间复杂度
虽然它不是一个满二叉树,但是算时间复杂度的时候是以最坏的情况来算。
递归函数的时间复杂度 = 递归总次数 * 每次递归中执行基本操作的次数
这个二叉树的节点个数为2^n-1,深度为n,
所以它的时间复杂度为O(2^n).
递归的空间复杂度是: 递归的深度*每次递归所需的辅助空间的个数
所以空间复杂度是:O(N)