网站备案登录密码找回,网站logo如何修改,如何网上卖自己的产品,做产品目录设计用什么网站好数据结构 | 算法的时间复杂度和空间复杂度【详解】
1. 什么是数据结构#xff1f; 数据结构(Data Structure)是计算机存储、组织数据的方式#xff0c;指相互之间存在一种或多种特定关系的数据元素的集合。 2. 什么是算法#xff1f; 算法(Algorithm):就是定义良好的计算过…数据结构 | 算法的时间复杂度和空间复杂度【详解】
1. 什么是数据结构 数据结构(Data Structure)是计算机存储、组织数据的方式指相互之间存在一种或多种特定关系的数据元素的集合。 2. 什么是算法 算法(Algorithm):就是定义良好的计算过程他取一个或一组的值为输入并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果。 3. 算法效率 算法效率是指算法执行的时间算法执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。在现在的计算机硬件环境中比较少需要考虑这个问题了特别是pc机的编程内存空间越来越大所以被考虑得也越来越少不过一个好的程序员都应该对自己的程序有要求每一个for比别人少一次判断1000个for就能够少掉很多的运行时间。所以能够理解能够大概的去运用效率度量还是有很大意义的。 算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。 时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算 机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。
4. 时间复杂度
4.1 时间复杂度的概念
时间复杂度的定义 在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。一 个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个 分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。 即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。 实际中我们计算时间复杂度的时候其实并不需要计算精确的执行次数而只需要知道大概执行次数所以这里我们引入了大O的渐进表示法。其中大O符号是用于描述函数渐进行为的数学符号。 案例1 请计算一下Func1中count语句总共执行了多少次 如果用一个函数F(N)来解释的话怎么解释【F(N) N*N 2N 10】这是一个函数式 这并不方便我们进行比较能不能简化一下 这里的时间复杂度是要取影响最大的项 大O渐进表示法估算–O(N^2)–O(N) 我们这里不关心硬件相同的配置N比N^2的程序要快 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);
}Func1 执行的基本操作次数 N 10 F(N) 130N 100 F(N) 10210N 1000 F(N) 1002010 实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。 4.2 推导大O阶的方法
大 O 表示法是一种计算机科学和算法分析中常用的渐进表示法用于描述算法的时间复杂度和空间复杂度。它帮助我们衡量算法在输入规模增加时运行时间或内存使用的增长趋势而不需要精确地测量或比较具体的运行时间。 大 O 表示法使用 “O(f(n))” 的形式其中 “f(n)” 表示输入规模 “n” 的函数。这意味着当输入规模足够大时算法的运行时间或内存使用将以 “f(n)” 函数的方式增长。以下是一些常见的大 O 表示法及其含义 O(1)常数时间复杂度 表示算法的运行时间不受输入规模的影响无论输入有多大运行时间都是固定的。O(log n)对数时间复杂度 表示算法的运行时间以对数方式增长通常见于二分查找等分治算法。O(n)线性时间复杂度 表示算法的运行时间与输入规模线性增长随着输入规模增加运行时间也会线性增加。O(n log n)线性对数时间复杂度 表示算法的运行时间随着输入规模的对数线性增加常见于快速排序和归并排序等算法。O(n^2)二次时间复杂度 表示算法的运行时间与输入规模的平方成正比通常见于嵌套循环等情况。O(n^k)多项式时间复杂度 表示算法的运行时间与输入规模的 k 次方成正比其中 k 为常数。O(2^n)指数时间复杂度 表示算法的运行时间随着输入规模的指数级增长通常表示算法的效率非常低。O(n!)阶乘时间复杂度 表示算法的运行时间随着输入规模的阶乘级增长通常表示算法的效率非常低。大 O 表示法的目的是为了提供算法效率的一种抽象概念让人们能够更容易比较不同算法的性能并估计它们在大规模输入下的行为。通过了解算法的大 O 复杂度开发者可以选择合适的算法来解决问题以便在实际应用中获得更好的性能。 使用大O的渐进表示法以后Func1的时间复杂度为 N 10 F(N) 100N 100 F(N) 10000N 1000 F(N) 1000000 4.3 常见时间复杂度计算举例 接下来就看看下面这几个案例相信你看完就有一定的了解 实例2 计算Func2的时间复杂度 我们前期就一点一点的算F(N) 2N 10时间复杂度是什么?【O(N)】就是取最大的那一项当N无限大的时候N和2N没有区别所以系数要去掉时间复杂度不是算次数是算量级
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);
}实例3 计算Func3的时间复杂度 如果不确定M和N的关系可能M很大可能N很大– O(MN)或者O(max(M,N))如果N远大于M–O(N)如果M远大于N–O(M)如果N和M差不多大–O(N) or O(M)
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);
}实例4 计算Func4的时间复杂度 这里可以看到k循环了100次那么他是O(100)吗【不是】是O(1)
注意 O(1)并不是代表一次而是常数次
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}小结一下
大O阶的方法 用常数1取代运行时间中的所有加法常数在修改后的运行次数函数中只保留最高阶项取决定性的那一项如果最高阶项存在且系数是不唯1的常系数则去除最高项的系数得到的结果就是大O阶如果最终结果是O(1)则表示常数次并不是代表一次还有就是没有小o阶~~ 实例5 计算strchr的时间复杂度 const char* strchr(const char* str, int character);while (*str) {if (*str character)return str;str;
}这个函数有可能有的同学没有见过这是C语言库里面的一个函数strchr是定位字符串中出现的第一个字符可能在前面的位置找到了最好肯在中间的位置找到了平均还有肯在最后的位置找到了最坏
小结一下 最坏情况 任意输入规模的最大运行次数上界 平均情况 任意输入规模的期望运行次数 最好情况 任意输入规模的最小运行次数下界一般我们比较关心的是一个算法的最坏情况 如果有最好最坏平均那么时间复杂度是一个保守的估算是取最坏这是最好的
实例6 计算BubbleSort的时间复杂度 很多同学一眼看他是O(N^2)那么他是O(N^2)吗接下来接着看
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;}
}再来看一个这个相比上一个的时间复杂度是什么可能有点同学一看这个循环有两层那么他是O(N^2),它是O(N^2)吗–继续接着往下看
int PartSort1(int* a, int left, int right) {int keyi left;while (left right) {while (left right a[right] a[keyi]) {--right;}while (left right a[left a[keyi]]) {left;}Swap(a[left], a[right]);}Swap(a[left], a[right]);
}我们上面都是看的循环但是我们要看思想不能只看循环第一个是–O(N^2)第二个是O(N)
你算对了吗
首先我们先看第一个冒泡排序的时间复杂度如图 再来看第二个 PartSort1当left和right相遇时时间复杂度是O(N) 小结一下
时间复杂度不能数代码中的循环而是需要根据思想进行灵活计算 实例7 计算BinarySearch的时间复杂度
这里一眼看就是一个二分查找~~我们这里的是不是复杂度数O(N)?
int BinarySearch(int* a, int n, int x)
{assert(a);int begin 0;int end n - 1;// [begin, end]begin和end是左闭右闭区间因此有号while (begin end){int mid begin ((end - begin) 1);if (a[mid] x)begin mid 1;else if (a[mid] x)end mid - 1;elsereturn mid;}return -1;
}首先先说结论这里是O(logN)我们这里看代码是看不出来的要看思想~~首先二分查找的前提是有序 这个数组假设有n个值 n/2/2/…/2 1最坏的情况~~ 我们这里除了多少个2找了多少次就除了多少个2 假设找了x次–2^x N -- x logN 我们这里的这个以2为底的logN是不是很不好写…我们平时就可以不写了~~直接写成O(logN) 但是有的书或者博客上面写成O(lgN)我们不建议~~和我们数学里面是有些混淆的 学了复杂度我们要指定O(logN)是一个很腻害的算法我们下面进行对照~~ 这里对应的有暴力查找数组过一遍查找O(N)二分查找O(logN)
比如
如果我把中国所有人的信息放到一个数组中我们要找多少次 我们就只需要找31次是不是很厉害~~ 我们这里前提是要有序有序是要有代价的需要排序如果有一个新生儿出生了就要插入如果有人离世了就要删除了这就很难~~这里有更好的数据结构有AVL树红黑树哈希表这些我们后面都会讲解~~
实例8 计算阶乘递归Fac的时间复杂度 首先来看这是一个阶乘很多同学肯一看是O(1)又不太敢确认我们先说结论—O(N)
long long Fac(size_t N)
{if (0 N)return 1;return Fac(N - 1) * N;
}阶乘是不是有多次函数的调用每次调用是常数次O(N)有N次调用就是O(N)~~ 我们再来变一下形~~我们来看下面这个的时间复杂度是多少呢 我们先说结果–O(N^2)然后我们进行分析~~
long long Fac(size_t N)
{if (0 N)return 1;for (size_t i 0; i N; i){//....}return Fac(N - 1) * N;
}这里是咋算的每次递归走了一次循环递归计算的是多次调用累加多少次调用N次调用每次调用多少趟这不是N每次都在变化当N为10时循环走10次当N是9时循环走9次递归次数累加是一个等差数列 0~N的等差数列所以就是O(N^2)~~
实例9 计算斐波那契递归Fib的时间复杂度 斐波那契数列类似于细胞分裂一个分裂成两个两个分裂成4个…
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}这里仔细看这是一个等比数列和~~ 这里可以用到错位相减法如图 根据大O渐进表示法时间复杂度也就是O(2^N)这是一个成指数增长的~~
5.空间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时额外占用存储空间大小的量度。空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。注意 函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
案例1 计算BubbleSort的空间复杂度 这里的这个空间复杂度是多少—O(N)还是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;}
}我们在上面说过空间复杂度算的是变量的个数对一个算法在运行过程中临时额外占用存储空间有没有开辟临时的空间有它们都是常数个所以就是O(1) 下面这种算法是经典的O(N) 案例2 计算Fibonacci的空间复杂度 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;
}这里我们malloc了·n1·个空间其他的都忽略掉所以就是O(N)
案例3 计算阶乘递归Fac的空间复杂度 long long Fac(size_t N)
{if (N 0)return 1;return Fac(N - 1) * N;
}这里递归空间复杂度计算也是空间累加但是不同的是空间可以重复利用所以这里就是O(N) 6.复杂度的oj练习
6.1 消失的数字
OJ链接
这里题目要求在时间复杂度上O(n)我们介绍三种方法看看哪种方法适合这道题~~ 方法一
先冒泡排序遍历当前值1不等于下一个数 这个时间复杂度是O(N^2) 方法二
将数组的每个元素异或0遍历再将异或出来的结果每个再异或 这个时间复杂度是O(N) 方法三
0到n等差数列公式计算和((首项 尾项) * 项数)/2依次减掉数据中的值剩下的就是消失的数字 这个时间复杂度是O(N) 可见只有方法二和方法三符合题目要求下面我们就写一下这个代码
方法二的代码
int missingNumber(int* nums, int numsSize){int N numsSize;int sum ((0N)*(N1))/2;for(int i 0;inumsSize;i){sum-nums[i];}return sum;
}方法三的代码
int missingNumber(int* nums, int numsSize){int x 0;for(int i 0;inumsSize;i){x^nums[i];}for(int i 0;inumsSize;i){x^i;}return x;
}6.2 旋转数组
OJ链接 我们这个题肯有些同学在C语言的时候做过 我们先来看思路一 思路一的时间复杂度是多少 可能有的同学算出来的是O(N*K)不完全正确~~ 最好的情况k % N 0k 7旋转0次是O(1)。k是N的倍数时不需要旋转~~最坏的情况k % N N - 1时比如13次旋转的最多20次最多…所以这个题的真正复杂度是ON*(N-1)—O(N^2) 那么我们要求时间复杂度是O(N)那么我们怎么优化呢 我们这里就要看思路二 这里很明显是O(N)
代码如下
void reverse(int* nums,int left,int right){while(leftright){int tmp nums[left];nums[left] nums[right];nums[right] tmp;left;right--;}
}
void rotate(int* nums, int numsSize, int k){if(knumsSize){k %numsSize;}reverse(nums,0,numsSize-1);reverse(nums,0,k-1);reverse(nums,k,numsSize-1);
}注意这里k一定要%numsSize否则会报错~~ 思路三 空间换时间 这里的时间复杂是O(N)空间复杂度是O(N)
代码如下
void rotate(int* nums, int numsSize, int k) {k % numsSize;int tmp[numsSize];int j k;//拷贝前n-k个for (int i 0; i numsSize - k; i) {tmp[j] nums[i];}//拷贝后k个j 0;for (int i numsSize - k; i numsSize; i) {tmp[j] nums[i];}//拷贝回原数组for (int i 0; i numsSize; i) {nums[i] tmp[i];}
}好了数据结构的算法的时间复杂度和空间复杂度到这里就结束了~~ 如果有什么问题可以私信我或者评论里交流~~ 感谢大家的收看希望我的文章可以帮助到正在阅读的你
