【算法笔记】时间复杂度与空间复杂度

前言我们写程序来解决具体问题时有时候会想到不同的解决方法也就是算法但该以什么来衡量这个算法的好坏呢我们主要以时间复杂度主要和空间复杂度来衡量这个算法的好坏1.时间复杂度1.1定义在近代中电脑硬件发展的速度非常快比如我们耳熟能详的摩尔定律就是在这个背景下诞生的CUP的运算速度的越来越快像是一些比较垃圾的CUP都能有每秒几亿次的计算效率 而内存的发展更是所以我们在衡量一个算法的好坏的时候我们一般主要关注时间复杂度。时间复杂度并不是指每个时间段这个程序的运行速率因为这个东西很受硬件的影响比如我的电脑比你的电脑好很多的话我更快的出了结果难道我写的程序就一定比你好吗这样比较显然是不公平的所以我们说的是时间复杂度但是我们关注的其实是这个程序的运行次数比如在下面的函数中void fun1() { int sum 0; for (int i 1; i 2 * n; i) { sum i; sum; } int k 7; while(k--) { sum k; } cout sum endl; }这个函数的运行次数就是2 * n 7次至于为什么是这个呢for循环里不是执行了两个语句难道不是4 * n吗前面也说过由于现在的CUP运算速度足够快说以我们一般只关注这个程序的循环执行次数而不关心里面具体的语句数量当然不能粗暴的只看外层的循环我们还得视具体的逻辑来判断。因此我们也可以不关心后面的常数项比如后面那个7次减减。我们一般使用大O来表示一个算法的复杂度这个程序的复杂度就为n的级别n前面的那个系数我们也是不关心的不管是2n还是3n我们都认为复杂度为n原理和不管常数项的处理是一样的而且我们一般只关注影响最大的那一项,比如当一个程序的运行次数式子同时存在n 和 n ^ 2 时我们认为他的时间复杂度为On ^ 21.2一些例子和常见的时间复杂度void fun2() { int sum 0; for (int i 1; i m * n; i) { // } while(n--) { // } cout sum endl; }这个程序的执行次数就是n * m n, 用大O表示法就是O(n * m)级别的但当这个m和n相近时我们也可以认为O(n ^ 2)int fun3(int n) { if (n 3) return 1; return fun3(n - 2) fun3(n - 1); }这个是计算斐波那契数列的递归函数这个函数在每次调用自己时都会展开两项所以它的时间复杂度就是O(2^n)级别的一般当时间为O(n^3)我们就认为这个时间复杂度已经很高了更何况是指数级别的这种时间复杂度一般放OJ都会超时的它的展开图可以大致认为是下面黑色的因为返回比较早就没展开到一个完成的三角形但我们还是可以认为它的时间复杂度为指数级别的我们也可以通过一些方法来优化比如记忆化搜索这个后面我应该会有更新可以优化为一个n的时间复杂度int fun4(int n) { if (n 1) return 1; return n * fun4(n - 1); }这个函数会展开n - 1次所以我们认为它的时间复杂度为O(n)上面就是常见的时间复杂度下面的表是一些补充表达式大O表示法阶数999999O(1)常数阶3n 7O(n)线性阶n^2 5n 10O(n^2)平方阶2\log_2 n 5O(\log n)对数阶n 3n\log_2 nO(n\log n)n\log n 阶2n^3 3n^2 4nO(n^3)立方阶2^nO(2^n)指数阶当2为对数的底数时可以忽略关于其他的一些对数时间复杂度我认为还是讲到一些算法比如分治、二分时顺便讲解它的时间复杂度会更好2.空间复杂度1.1定义程序在运行时会有压栈和出栈的操作一个函数在内存中也需要开辟空间来运行这会对内存造成一定的消耗。空间复杂度也同样可以使用大O表示法来表示它的空间复杂度方法也和计算时间复杂度非常的相似同时我们也不太关注空间复杂度下面我就举一些简单的例子来讲解1.2一些空间复杂度例子void sort(std::vectorint arr) { int n arr.size(); for (int i 0; i n - 1; i) { for (int j 0; j n - i - 1; j) { if (arr[j] arr[j 1]) { int temp arr[j]; arr[j] arr[j 1]; arr[j 1] temp; } } } }这是一个非常简单的冒泡排序这里我并没用对这个原本的顺序表进行引用操作所以它会在内存中重新开辟一个大小为n的动态顺序表至于是几n的我们也不关心所以它的空间复杂度为O(n)void rev(std::vectorint arr) { int left 0; int right arr.size() - 1; while (left right) { int temp arr[left]; arr[left] arr[right]; arr[right] temp; left; right--; } }这是一个反转数组的函数这里我对原数组进行了引用并没有额外的空间消耗所以它的空间复杂度为O(1)级别的int fun4(int n) { if (n 1) return 1; return n * fun4(n - 1); }这个函数会调用自身n-1次每一次调用都会占用内存所以它的空间复杂度为O(1)级别的完结