数据结构之时间.空间复杂度分析-蒲公英云

数据结构之时间.空间复杂度分析

#include <iostream>
#include <assert.h>
using namespace std;
/*
在很多数据结构的面试题中看似简单，但是对题目的要求却挺高，主要就体现在复杂度分析方面。复杂度又分为时间复杂度和空间复杂度。
1.时间复杂度
时间复杂度实际就是函数，函数计算执行的基本操作次数 .
在进行时间复杂度分析时需注意:
1)时间复杂度强调的是函数执行的操作次数，这里的函数是指数学里面的函数，而不是C语法里的函数；
2)在实际中我们通常情况考量的是算法的最坏情况；
3)忽略掉常数；
4) 关注运行时间的增长趋势，关注函数式中增长最快的表达式,忽略系数;
(比如：F(n)=10*n^3+50n+1000,其时间复杂度为O(n)=n^3)
5)递归算法的时间复杂度计算：递归总次数*每次递归次数.
2.空间复杂度
空间复杂度，它是对一个算法在运行过程中临时占用存储空间大小的量度。所以它强调的是使用的辅助空间的的大小，而不是指所有的数据所占用的空间。
要注意的是递归算法的空间复杂度，假如递归深度为N*每次递归的辅助空间大小，如果每次递归的辅助空间为常数，则空间复杂度为O(N)。
*/
//这是非递归的另一种算法，函数真正执行次数依然为n - 1, 所以忽略常数后，时间复杂度还是O(n);
//由于采用变量交换的方式，所以在这里辅助空间个数为一个常数，空间复杂度为O(1).
long long* fib(long long n)
{
    //如果表达式的值为假，整个程序将退出，并输出一条错误信息。如果表达式的值为真则继续执行后面的语句
    assert(n >= 0);                                /*执行1次*/
    long long* ptr = new long long[n + 1];        /*执行1次*/
    ptr[0] = 0;                                    /*执行1次*/
    ptr[1] = 1;                                    /*执行1次*/
    for (int i = 2; i <= n; ++i)                /*执行n-1次*/
    {
        ptr[i] = ptr[i - 1] + ptr[i - 2];        /*时间复杂度为O(1)的程序步骤序列*/
    }
    return ptr;                                    /*执行n-1次*/
}
//递归算法的空间复杂度计算方法是：递归深度*每次递归所需的辅助空间个数.
//递归栈空间(递归函数所需要的栈空间通常称为递归栈空间)包含形参a和n以及返回地址空间
//对于a,需要保留一个指针(4)拿32位计算机来说，指针所占的内存空间一般为4个字节 拿64位计算机来说，指针所占的内存空间一般为8个字节
//而对于n则需要保留一个int类型的值(也就是4字节) 如果返回地址也是4个字节 那么一次递归调用所需的辅助空间为12
//递归深度为n+1  所以递归栈空间需要12(n+1)
//SrSum = 12(n+1)=递归深度*每次递归所需的辅助空间个数.
//递归算法的时间复杂度计算方法是:递归总次数*每次递归次数；
template <class T>
T rSum(T a[], int n)                /*时间复杂度为O(n)的程序步骤序列*/
{
    //返回数组元素a[0：n-1]的和
    if (n > 0)
    {
        return rSum(a, n - 1) + a[n-1];
    }
    return 0;
}
int main()
{
    int a[3] = {1,2,3};                    /*执行1次*/
    int sum = rSum(a,3);                /*执行1次*/
    int b = sizeof(int *);
    system("pause");
    return 0;
}
//1)假设以最坏情况考虑，二分查找第一次在n / 2中查找(n为元素个数)；第二次在一半的一半中查找，
//即n / 2 / 2 = n / 4; ……第x次在n / 2 ^ x范围内查找，即2^x = n(x = log2^n), 所以时间复杂度为O(log2^n).
//2)递归情况下的空间复杂度：递归深度为N*每次递归的辅助空间大小，如果每次递归的辅助空间为常数，则空间复杂度为O(N)。
//对于递归的二分查找，递归深度是log2^n，每次递归的辅助空间为常数，所以空间复杂度为O(log2^N)
int BinarySearch2(const int* ptr, const int x, const int left, const int right)
{
    int mid = (left + right) / 2;
    while (left <= right)
    {
        if (x<ptr[mid])
        {
            return BinarySearch2(ptr, x, left, mid - 1);
        }
        else if (x>ptr[mid])
        {
            return BinarySearch2(ptr, x, mid + 1, right);
        }
        return mid;
    }
}
//对于非递归的二分查找与递归查找的时间复杂度一样的分析方法, 所以时间复杂度为O(log2^n)；
//但是在这个过程中，辅助空间为常数级别，所以空间复杂度为O(1)
int BinarySearch1(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;
}