数据结构_时空复杂度

数据结构_时空复杂度

前言：此类笔记仅用于个人复习，内容主要在于记录和体现个人理解，详细还请结合bite课件、录播、板书和代码。

[toc]

算法效率

算法效率是用来衡量一种算法的好坏的指标 简洁的代码不一定好，比如典型的斐波那契数列 衡量算法的好坏要看时间复杂度和空间复杂度 时间复杂度衡量的算法的运行快慢 空间复杂度衡量的是算法运行时需要额外开辟的空间

时间复杂度

时间复杂度本质上是一种函数

表示方法：大O的渐进表示法

1. 时间复杂度是算法中基本语句（或者说基本操作）的执行次数，不是秒数
2. 是一种“悲观”的表示法 一般计算的都是最大的执行次数
3. 计算的是量级，不是具体的确切数字

推导O的方法

1. 用常数 1 代替运算时间中的所有加法常熟（因为量级是常数级）
2. 在修改后的运行次数函数中，只保留最高阶 因为对于量级来说，只有最高阶有决定性作用
3. 如果最高阶存在不是 1，则把最高阶的常数系数换为 1

递归算法时间复杂度

1. 每次函数调用是O(1)，那么就看它的递归次数（函数调用次数就是函数体中的运算次数，如果没有循环一般就是O(1) ）
2. 每次函数调用不是O(1)，那么就看它的递归调用中次数的累加

几个例子

// 计算Func2的时间复杂度? 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); }基本语句（或者说基本操作）执行了2N+10次，大O渐进表示法就是O(N) N是数据规模 ， 数据规模越大，复杂度的差距越大，算法的优劣体现的就越明显 基本语句（或者说基本操作）的执行次数成为时间频度，在上面的例子中T(N)=2N+10 // 计算Func3的时间复杂度? 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); }基本操作执行了M+N次，而带入到算法中的数据规模也有两个，分别是M和N，因此是O(M+N) // 计算Func4的时间复杂度? void Func4(int N) { int count = 0; for (int k = 0; k < 100; ++ k) { ++count; } printf("%d\n", count); }O(1) const char * strchr ( const char * str, int character );这是字符查找函数，返回在参数（字符串）中第一次出现要查找的字符的位置 通过遍历的方式查找，最好是第一次就能找到，最坏是第N次，因此是O(N) // 计算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-1次 最坏的情况是顺序是完全相反的 若初始文件是反序的，需要进行n-1趟排序。每趟排序要进行n-i 次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值 ———百度百科 执行次数是(N*(N+1)/2次，按照大O表示法就是O(N^2) 因此时间复杂度就是O(N^2) 并不一定有几层for循环，时间复杂度就有N的几次方，只是有的时候是这样的 // 计算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 } }二分查找，又称折半查找，前提是数组必须是有序的c 通过与每次与有序数组的中间元素进行大小比较，将范围缩小为原来的一半 最好的情况是第一次就找到（要查找的正好是中间元素），最坏的情况是找不到（那就要找到底），是logN次（底数为2） O(logN) 一般由于以2为底的log出现的频率非常大，计算机打出log2这个符号比较困难，一般就认为log就是log2 // 计算阶乘递归Fac的时间复杂度? long long Fac(size_t N) { if(0 == N) return 1; return Fac(N-1)*N; }调用次数是O(1) 递归次数是N O(N) // 计算斐波那契递归Fib的时间复杂度? long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2); }这个斐波那契函数函数调用次数是O(1) 递归次数是2^N

O(2^N)

空间复杂度

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用空间大小的量度 空间复杂度计算的不是在算法运行过程中占用的系统的bytes(字节)数，因为这样也没什么意义 计算的是变量个数 计算规则也是大O的渐进表示法 注意: 函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了，因 此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 几个例子 1. // 计算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; } }变量是具有作用域的，出了作用域就会释放，将权限归还给操作系统，不算占用 每次进入for循环的时候只生成一个额外的变量 O(1) 2. // 计算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; }动态开辟数组为N个，O(N) 3. // 计算阶乘递归Fac的空间复杂度? long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; }递归调用了N次，一共开辟个N个栈帧，每个栈帧使用了常数个空间，空间复杂度是O(N) 4.

两个for循环里的条件判断都是<=n，处理都是++ 第一层循环执行次数是n，第一层下第二层循环是n-2^i^ 所以是O(n^2^)

相比于空间复杂度，算法的时间复杂的更重要一些，现在内存生产技术逐渐提高，计算机内存逐渐变大，内存的成本低于时间的成本，因此也有了一些”用空间换时间“的算法

常见复杂度

qSort（快速排序）：O(N)

时间复杂度对照表格：

一道小题 将下列函数，按它们在n→∝时的无穷大阶数，从小到大排序。 n， n-n^3^+7n^5^， nlogn， 2^n/2^， n^3^， logn， n^1/2^+logn， (3/2)^n^， n!， n^2^+logn 从小到大排列为：logn < n^1/2^+logn < n < nlogn < n^2^+logn < n^3^ < n-n^3^+7n^5^ < 2^n/2^ < (3/2)^n^ < n!

一些题目

1.消失的数字 OJ链接

方法一：排序 冒泡O(N^2) qsort(N*logN) 方法二：映射 根据元素个数重新开辟一个元素个数为size的数组new，元素初始化为-1。遍历原数组中的每个数n，并按顺序映射到new中，new[n]=n。最后new中仍为-1的权重就是消失的数字。

方法三：异或 按位异或 异或运算：比较两个十进制数字的二进制形式，每个二进制位进行比较，每个二进制位相同为0，相异为1，多个数字比较时不用考虑顺序（不影响结果）

解题思路： 定义一个val赋值为0，先依次跟0-n异或，并把结果赋值给自己（val^=) 然后再跟数组里的每个元素异或，最后得到的结果就是消失的数字

因为异或顺序不影响结果，相当于

这样0-n跟数组中如果有重复的数字，异或之后结果为零，数组中消失的数字在0-n中落单，跟val（值为零）异或之后值还是它本身。 基本操作的执行数是T(N) = (N-1)+N O(N) 方法四： 利用等差数列计算 0-n本身就是一种等差数列，根据求和公式减去数组各元素，剩下的值就是消失的数字 O(N) 2.旋转数组OJ链接 输入：nums = [1,2,3,4,5,6,7] , k=3 输出：[5,6,7,1,2,3,4] 方法一： 重新开辟一个长度为n的数组news，nums的后k项赋值给new的前k项，前n-k项复制给new的后n-k项 时间复杂度O(N) 空间复杂度O(N) 方法二： 右旋k次，一次移动一位（最后一个元素赋值给tmp，前面的元素依次向前赋值）

每次时间复杂度是N，一共执行k%N次，总计N*(k%N)次 如果k%N=1，那么时间复杂度是O(N) 如果k%N=N-1，那么时间复杂度是O(N^2)，这种情况是最差的 所以时间复杂度是O(N^2) 空间复杂度是O(1) 方法三：用规律

时间复杂度O(N) 空间复杂度O(1)

追加的内容

时间一去不复返，是累积的 空间回收以后可以重复利用 栈是向下生长的，下面返回之后被销毁，返回到上面，再向下开辟空间（用的是之前的同一块空间） 栈上用完就销毁，再用的时候就又被覆盖 空间的销毁指的是交还使用权，栈不大，但是是可以重复利用的

（详细建议复习一下鹏哥的栈帧）

结束

That’s all, thanks for reading!💐