【数据结构】时间复杂度和空间复杂度

目录

一.什么是数据结构

二.什么是算法

三.算法效率

四.时间复杂度

定义：

大O的渐进表示法

例题：

例1：

例2：

 例3：

 例4：

例5：

例6：

常见时间复杂度

五.空间复杂度

定义：

常见空间复杂度

例题：

例1：

例2：

 例3：

例4:

六.常见复杂度对

---

一.什么是数据结构

数据结构(Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的
数据元素的集合。
 

二.什么是算法

算法(Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。
 

三.算法效率

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度：衡量一个算法的运行快慢

空间复杂度：衡量一个算法运行需要的额外空间。

在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
空间复杂度早期关注，随着电脑内存越来越大，空间复杂度渐渐不被关注

四.时间复杂度

定义：

算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。

环境不同（机器不同），具体运行时间就不同，时间复杂度不是指时间，而是指算法中的基本操作的执行次数，为算法的时间复杂度

大O的渐进表示法

大O符号：是用于描述函数渐进行为的数学符号

1. 用常数1取代运行时间中的所有加法常熟
2. 在修改后的运行次数函数中，只保留最高阶项
3. 如果最高阶项存在且不是1，则去除与这个项目相乘的常熟。得到的结果就是大O的阶

通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
 

有时候，我们会发现，一些代码的时间复杂度存在最好、平均和最坏情况：

最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
在实际情况中一般关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为最坏情况。

例题：

例1：

//计算Func1的时间复杂度
void Func1(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	int M = 20;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

时间复杂度为O(N)

函数内for循环循环了2N次，虽然下面while循环循环了20次但20是常量，不计入时间复杂度。

而与未知数相乘的常数可以去除，最后为N

2N+10 --->  2N --->  2N和N随着N的值不断变大，差距越来越小，在巨大数字的面前可以忽略不计

例2：

//计算Func2的时间复杂度
void Func2(int N,int M)
{
	int count = 0;
	for (int k = 0; k < M; ++k)
	{
		++count;
	}
 
	for (int k = 0; k < N; ++k)
	{
		++count;
	}
	printf("%d\n", count);
}

 时间复杂度为O(N+M)

如果：

M远大于N  --->  O(M)

N远大于M  --->  O(N)

M和N差不多大  --->  O(M)或O(N)

 例3：

//计算下面循环的时间复杂度
while(*str)
{
    if(*str == character)
       return str;
    else
       ++str;
}

str = "Hello word"   （str内的值不唯一）

查找元素	时间复杂度	情况
h	O(1)	最好情况：任意输入规模的最小运行次数（下界）
w	O(N/2)	平均情况：任意输入规模的期望运行次数
d	O(N)	最坏情况：任意输入规模的最大运行次数（上限）

• 当一个算法随着输入不同，时间复杂度不同。
• 当求一个函数的时间复杂度时，求的是最坏的情况下的时间复杂度

 例4：

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int exchange = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i-1] > a[i])
            {
                Swap(&a[i-1], &a[i]);
                exchange = 1;
            }
        }
        if (exchange == 0)
            break;
    }
}

在最外层循环内，需要循环n次，在大循环内还要再循环，第一次循环是n次，第二次是n-1次，依次递减。

 我们要计算时间复杂度，可以看出是将小循环全部相加，那就是等差数列相加。

为：(n+1)*n/2 = (n^2+n)/2

根据大O的渐进表达式可知为O(n^2)

例5：

// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
    if(0 == N)
        return 1;
    return Fac(N-1)*N;
}

该代码为递归，共进行了N次递归，时间复杂度为O(N)

例6：

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
    if(N < 3)
        return 1;
    return Fib(N-1) + Fib(N-2);
}

该函数为斐波那契数列，我们可以由图得出它的时间复杂度：

对于斐波那契数列，我们都知道，越往下，递归可能会在右边断掉，但是对于时间复杂度而言，我们求的是一个模糊的概念，断掉的那部分相对于整体而言是无伤大雅的，我们可以看出这是一个等比数列，可以根据等比数列求和算出为2^(n-1)-1.

由大O的渐进表达式就可以得出它的时间复杂度为：O(2^n)

常见时间复杂度

常熟阶O(1)

对数阶O(logN)

线性阶O(n)

线性对数阶O(nlog2)

平方阶O() 

立方阶O()

k次方阶O()

五.空间复杂度

定义：

空间复杂度是：临时占用存储空间大小的量度

• 空间复杂度不是指程序占用多少空间，这没有意义，空间复杂度算的是函数内创造的变量占用的空间个数
• 同样使用大O的渐进表示法
• 函数运算时需要的栈空间（存储空间、局部变量、一些寄存器信息等）在进入函数前已经确认好，不计入空间复杂度，因此空间复杂度主要通过函数在运行时显示申请的额外空间来确定

常见空间复杂度

O(1)

O(n)

O()

例题：

例1：

int BinarySearch(int* a, int n, int x)
{
	assert(a);//查看指针a是否为空，不影响判断空间复杂度
 
	int begin = 0;
	int end = n;
	while (begin < end)
	{
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid;
		else
			return mid;
	}
	return -1;
}

空间复杂度O(1)

只创建了三个变量，为常数，计为O(1)

例2：

int Fac(int N)
{
	if (N == 1)
		return 1;
 
	return Fac(N - 1) * N;
}

空间复杂度O(N)

每次递归后，创建新的栈区，此函数可以看作创建了n个栈区

 例3：

int* m = (int*)malloc(sizeof(int)*n);
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

空间复杂度O(N)

malloc创建了n个新空间

例4:

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
    if(N < 3)
        return 1;
    return Fib(N-1) + Fib(N-2);
}

这又是一个斐波那契数列，但与时间复杂度不同的是，空间是可以重复利用的。

 递归是先从N开始一直到2，在返回之后在递归。

 当达到空间利用到N-1时，就会销毁空间，返回值，在下次利用空间时，利用的是销毁的空间，这样斐波那契数列的空间复杂度为O(N)

六.常见复杂度对