你真搞懂时间复杂度和空间复杂度了吗 _复杂度

要须心地收汗马，孔孟行世目杲杲。这篇文章主要讲述你真搞懂时间复杂度和空间复杂度了吗相关的知识，希望能为你提供帮助。
@toc
写在前面说实话，我已经学了不少的数据结构了，第一次接触时间和空间复杂度的时候感觉有些不好理解，这篇博客就搁置下来了。这些天感觉自己理清楚了。所以开始和大家分享。要是有什么错误的地方，还请大家指正.
看完我们就会发现,计算复杂度,我们就是计算一个大概,我们平常遇到的问题复杂度不是O(1)就是O(N),其他的一般很少见.
算法效率在谈复杂度之前，我们必须说一下什么是好的代码，好的代码本质就是耗费算力最少的代码，我们都知道斐波那契数列，下面让我们看看用递归方法来实现会怎么样

#include < stdio.h> int val = 0; int Fib(int n)val++; if (n < 3)return 1; return Fib(n - 1) + Fib(n - 2); int main()int n = 10; Fib(n); printf("递归执行的次数 : %d\\n", val); return 0;

文章图片

时间复杂度在看到这个时间一词后，我首先想到的是便是一个程序执行所用的时间。我想这就是时间复杂度的解释吧。可是现实给了我一巴掌。要是我们用时间来衡量一个程序的好坏。那么厉害的计算机一定吊打老式计算机，一个程序出现两种不一样的复杂度，这不是荒谬吗! 后来我查了一下定义。原来是程序的一些代码的==执行次数==,我们先来看下定义
大O渐进法我们计算时间复杂度和后面的空间复杂度都是使用大O渐进法，现在你可能还不太了解这是什么，后面你一看例子就可以明白了

// 请计算一下Func1中++count语句总共执行了多少次？ 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;

我们可以轻易算出++count语句语句执行的次数是==N^2^+ 2 * N + 10==,这对于我们来说是在是太简单了,so easy！！！那么这个函数的时间复杂度是O(N^2^) ？？？我写了什么？为何是这样的？下面我把大O渐进法的规则说一下

用常数1取代运行时间中的所有加法常数。
在修改后的运行次数函数中，只保留最高阶项。
如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶
看了规则后，我们还是一头雾水，这究竟什么跟什么，我是看不懂。大家不要担心我这里每一条都给出解释

用常数1取代运行时间中的所有加法常数。
我们可以看到N^2^+ ==2== * N + ==10==里面的 2 和 10 都是常数，都给我变成1得到 N^2^+N + ==1==
只保留最高阶项
从第一步得到的结果是N^2^+N + 1，我们只保留最高项，我们发现 ==N^2^==是最高项，就要它自己
如果最高阶项存在且不是1，则去除与这个项目相乘的常数
判断最高项的系数是不是 1 不是就给他变成1，假如最高项是 2N^2^，我们就把他变成 N^2^，这就是得到O(N^2^)
计算下面代码的时间复杂度我们已经初步了解了时间复杂度的算法，下面我们就用几个例子来巩固一下。不过这些例子都是我们经常看到的类型，大家最好把结果和思想记住
多个变量我们计算实际执行次数是 ==N + M==，由于不知道N和M的关系，随意时间复杂度就是 O(N+M) 。假如我们要是知道了M和N关系，比如说M< < N 那么时间复杂度就是O（N）
常数这个就更简单了，实际次数就是 100 那么时间复杂度就是 O（1）我们可能会有些疑惑，我们执行了1亿次是不是也是O（1），实际上是的，只要是常数次数就是O（1）
二分查找【你真搞懂时间复杂度和空间复杂度了吗】这个才是重点，我们对二分查找很熟悉，不过我们如何计算他的复杂度呢，对于这种我们可能有以下三种情况

最好情况只查找一次就找到了
平均情况查找多次才找到
最坏情况最后还没有找到

那么我们应该用那种情况来计算时间复杂度呢？我们可以想一下，如果我们把一个项目送给上司，对他说这个代码的时间复杂度是O(1)，但是当上司测试代码时候，发现很长时间才跑出了结果，你说他会怎么做:smile:我们应该考虑最坏情况，这也是大O渐进法所规定的。

// 计算BinarySearch的时间复杂度？ int BinarySearch(int* a, int n, int x)assert(a); int begin = 0; int end = n - 1; 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;

文章图片

递归对于递归的函数时间复杂度我们也计算函数递归的次数,计算递归函数的时间复杂度是一大难点，我们要是了解函数的栈帧可能会容易一些。不过不用太担心这些笔试一般不会出现太难的问题
单路递归

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

我们假设 N的初始值是　１０　后面会依次递归，直到　N　＝　０时，函数一共递归了N所以时间复杂度是O(N)。这里我无法用文字形象的表示出来，要是大家不理解可以在网上找些视频或者私信我。
多路递归

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

这个斐波那契数列的递归更加困难了。要是理解二叉树可能会更好理解一点。这里我们还使 N　＝　１０这样我们就理解了一点,没往下一层我们递归的次数 *2(一些细枝末节就不考虑了) .可以很轻易的知道我们有N层(实际小于N),那么时间复杂的就是 ==O(2^N^)==, 这就是我们最恶心的复杂度,也是很坏的代码.但我们N = 20时,会递归 1,048,576次.后面越来越恐怖

文章图片

空间复杂度空间复杂度的计算和时间复杂度的计算是一样了,都是使用大O渐进法,不过空间复杂度关注的使空间的大小.他比时间复杂度简单多了
我们还是来用例子演示

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;

为了解决这一问题,我们最多是的时候开辟了三个空间==end,exchange ,i== . 注意我们可能会对exchange 感觉到疑惑,他不是开辟了N次吗,是的,但是每一开辟的都是同一块空间,并且出了作用域就被销毁了.下面的例子可能会解决你的疑惑

// 计算Fibonacci的空间复杂度？ // 返回斐波那契数列的前n项 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;

这个空间复杂度是O(N),我们确实开辟了 N 个 long long类型的空间