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

爱被打了一巴掌 2022-05-25 10:53 172阅读 0赞

#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;
    }