审时度势 — 复杂度与是否可做
标签: 审时度势 — 复杂度与是否可做
学习人数: 18.3k


高清播放
赞赏支持

在做题之前,我们要先判断这道题是否可做,对于简单的模拟题,大家肯定都知道,我能写出来就是可做,写不出来就是不可做。但是对于循环嵌套和算法题,我们就需要去判断思考自己设计的算法是否可以通过这道题。

不懂复杂度计算的同学去看一下数据结构课程的第一章,很简单的。

 

例如:我们写一个冒泡排序,它是两个for循环,时间复杂度是O(N^2)

那么在1S内我们最多可以对多少个数进行冒泡排序呢,N在1000 - 3000之间。

一般情况下我们可以默认评测机一秒内可以运行1e7条语句,当然这只是一个大概的估计,实际上每个服务器的性能不同,这个值都不同,但是一般都相差不大,差一个常数是正常的。

 

因此,我们可以这样做一个对应,下面是时限1S的情况

O(N) ~ N最大在500W左右

O(NlogN) ~ N最大在20W左右

O(N^2) ~ N最大在2000左右

O(N^2logN) ~ N最大700在左右

O(N^3) ~ N最大在200左右

O(N^4) ~ N最大在50左右

O(2^N) ~ N最大在24左右

O(N!) ~ N最大在10左右

如果是2S、3S对应的乘以2和3就可以。

 

特殊技巧:如果发现自己设计的算法不能再题目要求的时限内解决问题,不要着急,可以先把这道题留一下,继续做其他题,然后看一下排行榜,有多少人过了这道题,如果过的人多,那么说明这道题可能数据比较水,直接暴力做,不要怕复杂度的问题,因为出题人可能偷懒或者失误了导致数据很水。考研机试的题目数据大部分情况都比较水,所以不要被复杂度吓唬住了,后面的章节会教大家面对不会更好的算法那来解决题目的时候,如何用优雅的技巧水过去。

 

举个简单的例子

题目要求你对10W个数进行排序

假设你只会冒泡排序,但是冒泡排序很明显复杂度太高了,但是有可能出题人的数据最多只有100个,根本没有10W个,那么你就可以用冒泡排序通过这道题。

但是这种情况比较少见,所以可以先把这道题放着做其他题,然后再看看其他人能不能通过,如果很多人都过了,那么你就可以暴力试一下。

 

特别注意:空间复杂度一般不会限制,如果遇到了再想办法优化空间。

登录查看完整内容


课后作业

学会分析算法的时间复杂度


登录后开始许愿

暂无评论,来抢沙发