[数据结构与算法] 数据结构时间复杂度和空间复杂度

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构时间复杂度和空间复杂度 -> 正文阅读

[数据结构与算法]数据结构时间复杂度和空间复杂度

1.时间复杂度

概念：算法中的基本操作的执行次数为时间复杂度（基本语句关于问题规模N总的执行次数的一个数学函数）

1.1大O的渐进表示法

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

#include<stdio.h>
void Func1(int N)
{
	int count = 0;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			++count;
		}
	}
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	}
	int M = 10;
	while (M--)
	{
		++count;
	}
	printf("%d\n", count);
}

这个函数的精确执行次数为F(N) = N^2 + 2N + 10

用大O渐进法表示了之后是O（N^2）

注意：:

1.时间复杂度并没有按照运行耗费的时间来衡量，而是一句基本语句的执行次数来衡量是因为不同及其的性能不一样，你用神威太湖之光跟我的本子一块跑斐波那契递归算法谁会更快呢？

2.跑一个程序会有很多的算法，对应的某一种算法还会有不同的情况比如拿二分查找举例子，我的mid直接就是我要找到的数字那我第一轮循环下来不就找到了，那我要找到的数字是在left 或者 right上面呢是不是又不一样了，所以对应一个算法他也有很多的时间复杂度有最快的最慢的而衡量一个算法时间复杂度一定是那个最慢的来衡量的。

有以下例题

例题1

void Func2(int N)
{
    int count = 0;
    for (int k = 0; k < 2 * N ; ++ k)
    {
        ++count;
    }
    int M = 10;
    while (M--)
    {
        ++count;
    }
    printf("%d\n", count);
}

F(N) = 2N + 10

O(N)

例题2

void Func3(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);
}

F(M,N) = M + N

O(M + N)

例题3

void Func4(int N)
{
    int count = 0;
    for (int k = 0; k < 100; ++ k)
    {
        ++count;
    }
    printf("%d\n", count);
}

F(N) = 100

O(1)

例题4

const char * strchr ( const char * str, int character );

这个strchr是strstr的一种strstr是前面传你要查找目标的字符串，后面是你要查找的字符串找到了返回第一次找到的地址，这个strchr则是变成了从目标字符串查找你要的字符，返回第一次出现这个字符的地址，那要是这个第一次出现是目标字符串的最后一个呢，哎时间复杂度不就出来了

F(N) = N

O(N) = N

例题5

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

这个就是很经典的冒泡排序了这个时间复杂度也很好想

也不难看出总的基本语句执行次数推广一下就是从1 ~ N - 1的等差数列前N项和

F(N) = (N^2 - N) / 2

O(N^2)

例题6

#include <stdio.h>
int binarysearch(int arr[], int size, int key) {
	int left = 0;
	int right = size - 1;
	while (left <= right) {
		int mid = (left + (right - left)) >> 1;
		if (key == arr[mid]) {
			return mid;
		}
		else if (key > arr[mid]) {
			left = mid + 1;
		}
		else if (key < arr[mid]) {
			right = mid - 1;
		}
	}
	return -1;
}
int main() {
	int arr[] = { 1,2,3,4,5,6,7,8,9 };
	int size = sizeof(arr) / sizeof(arr[0]);
	int key = 0;
	printf("你要在1-9查找哪一个数字?\n");
	scanf_s("%d", &key);
	int num = binarysearch(arr, size, key);
	if (num) {
		printf("找到%d了！下标是%d", arr[num], num);
	}
	else {
		printf("没找到个数字！");
	}
	return 0;
}

来说第一种方式

主要就是这一句right = size -1；这个我们要知道所有的运算其实都是下标运算如果是size - 1那就刚好匹配到数组下标每个数都可以找到，换而言之就是形成了一个左闭右闭的这个区间【left，right】

假设我们要找这个key为2

?进入循环第一次

之后我们的mid就是key了就直接返回了

为啥要每次循环是right = mid -1；呢以为这个是闭区间也就是可以找到right然而mid在上一轮已经比过了所以没必要在进行一次所以说mid - 1

为啥在循环条件里面有等于号呢，举个特例如果key是1 or 9你没有等于号的话1和9是找不到的，其实他的根本原因是你right是size - 1的问题你就导致你的数组内是可以索引到的，那什么时候停止呢带等于号的话while（left <= right）当left == right + 1就停止了，带入数字看一下【8.7】不可能有个数字大于8小于7吧！

接下来来说第二种方式
?

#include <stdio.h>
int binarysearch(int arr[], int size, int key) {
	int left = 0;
	int right = size;
	while (left < right) {
		int mid = (right + left) >> 1;
		if (key == arr[mid]) {
			return mid;
		}
		else if (key > arr[mid]) {
			left = mid;
		}
		else if (key < arr[mid]) {
			right = mid;
		}
	}
	return -1;
}
int main() {
	int arr[] = { 1,2,3,4,5,6,7,8,9 };
	int size = sizeof(arr) / sizeof(arr[0]);
	int key = 0;
	printf("你要在1-9查找哪一个数字?\n");
	scanf_s("%d", &key);
	int num = binarysearch(arr, size, key);
	if (num) {
		printf("找到%d了！下标是%d", arr[num], num);
	}
	else {
		printf("没找到个数字！");
	}
	return 0;
}

这个主要是这一句right = mid 刚刚不是要减1吗这块咋又不减了？
是因为你right赋值是size 我们知道这个left 和 right mid 都是下标你数组原本最大的下标是size - 1你却给他个size 我直接 arr[right] 是越界的，换而言之也就是说这时候的范围是【left，right）左闭右开的，下一次循环的时候 mid 就被剔除出去了你的搜索区间就是【left，mid）和【mid + 1，rigth）你right = mid 其实也就是 mid下标的前一个元素来比较。

假设我们要找这个key为2

最后arr[mid] == key找到了

这次循环退出的条件咋不能等于了while（left < right）那就是left == right 带入数字就是【8，8）你分开这个再去按照【left，mid）和【mid + 1，rigth）是空的找不了了。

然后就是这个算法的改进

也就是这一句

(right + left) >> 1

left + ((right - left) >> 1);

来防止溢出我们画个图来理解一下?

前者就可能造成溢出问题后者可能性就小要是left + right 很大超过 int 的21亿多一点点范围呢，这个left + right 的值还准确吗？

时间复杂度：

?我们可以看出来O( $\log2^N$ )

例题7

long long Fac(size_t N)
{
    if(0 == N)
        return 1;
return Fac(N-1)*N;
}

这个就是求阶乘的递归算法，对于递归呢就是把一个大的问题分解成一个个小的问题，一个个小的问题可以依赖同一种逻辑方法来完成，可能就是每一次传入的参数不同，也可把他看作一个循环。?

对于这种递推算法的时间复杂度是这样算的

递归算法的时间复杂度：单次调用的时间复杂度 * 总的递归次数

?举个特例fac()单词递归的时间复杂度一眼就能看出来O(1)

总的递归次数呢根据Fac(3)可以算出是2 推广一下那Fac(N)的递归次数就是N - 1了因为就一条递归的路最后一次直接就return 了也就是N - 1

那F(N) = N + 1

O(N) = N

例题8

long long Fib(size_t N)
{
    if(N < 3)
        return 1;
return Fib(N-1) + Fib(N-2);
}

这个比阶乘稍微能麻烦一点就是他的递归路程是两条，有点二叉树的感觉，单次递归调用的时间复杂度也是O(1)来看他的总的递归次数

你可以把Fib(3)的那一块挪到图示位置，这样总的递归次数就好算了，这就能看出来，每一次乘2

每一次乘2且Fib(6)只有三层，推广一下那Fib(N)有几层呢？那就是N - 3层这就是 2^0到2^(N - 3)的等比的前N - 2项和因为第一项是0次方这样就把O(N)算出来了

2.空间复杂度

概念：是对一个算法在运行时候中临时占用的存储空间大小的量度

看算法有没有开辟额外的辅助空间 malloc calloc ralloc

如果算法内部创建了一个数组，而数组创建必须要给出申请空间的大小，换而言之空间大小是一个常量。对于空间复杂度我们也采用大O渐进法来表示。

例题1

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

又是我们的老朋友冒泡排序，时间复杂度我们已经知道了那这个空间复杂度呢？看一眼没有借助辅助空间ok O( 1 )结束

例题2

long long Fac(size_t N)
{
    if(N == 0)
        return 1;
    return Fac(N-1)*N;
}

?这个跟上个题就不一样了，又是递归算法那递归算法的空间复杂度怎么算呢？

递归算法空间复杂度求解：

单次运行的空间复杂度 * 递归深度

递归的过程在这

?那他的深度是多少呢一眼就看出来了 4 推广N + 1

那好现在单次递归我只要知道了就可以了这里又要扯到我们老生常谈的一个东西了? 栈帧

每个函数在运行的时候系统都会给该函数分配一定大小的空间来存放局部变量，所需参数，运算的中间结果，以及一些寄存器的信息，栈帧是在栈上每次函数运行的时候由操作系统在栈上分配栈帧的大小在编译器编译代码的时候已经确定好了栈帧大小就是一个常量 O (1)

空间复杂度O( N )

?例题3

long long* Fibonacci(size_t n)
{
    if(n==0)
        return NULL;
    long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
    fibArray[0] = 0;
    fibArray[1] = 1;
    for (int i = 2; i <= n ; ++i)
    {
        fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
    }
    return fibArray;
}

斐波那契吗这次是递归吗？看清楚了哦！开辟N个空间结束O( N )