首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >客户端几乎不用的算法系列:复杂度估算的土方法

客户端几乎不用的算法系列:复杂度估算的土方法

作者头像
用户2932962
发布于 2019-12-11 06:36:22
发布于 2019-12-11 06:36:22
73900
代码可运行
举报
文章被收录于专栏:程序员维他命程序员维他命
运行总次数:0
代码可运行

想必大家都知道很多算法书上面的复杂度计算基础的”第一章节“,长到你不想看。但是不看吧又觉得失去了什么。所以这篇文章就来说说这个复杂度有没有什么通俗易懂的土方法来计算。

土法一:执行一段约是一次运算

我们假设计算机运行一段基础代码,就需要进行一次运算。也就是我们常常说的 O(1)

来写一段从 1 累加到 100 的代码:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
s = 0
for i in range(1, 101):
    s += i
print(s) # 5050

如此要循环 100 次,时间复杂度就是 O(100) 。如此,我们改变计算上届,将 100 扩大到 n ,这样便会发现使用循环的方法进行累加是一个时间复杂度为 O(n) 的算法。

我们将累加算法改成等差数列前 n 项求和来计算:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
s = (1 + 100) * 100 // 2 # 5050

如此,我们将一个 O(n) 的算法优化到了 O(1) 。这种优化无论是对于计算机,还是我们人脑,都可以大幅度的降低运算复杂度。

为什么说高斯是天才,因为他在小学三年级就发现了这个规律,并将一个 O(n) 的算法优化到了 O(1)

土法二:以经验计算时间

以前我在大学的时候参加 ICPC 竞赛有这么一个土方法:

一般的计算机,在处理 10^7 计算的时候需要消耗一秒的时间。可以写一个来验证一下:

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
import datetime

tot_time = 0

for t in range(0, 10):
    st = datetime.datetime.now()
    sum = 0
    for i in range(0, 10000000):
        sum += i

    ed = datetime.datetime.now()
    inv = ed - st
    tot_time += inv.microseconds / (10 ** 6)
    print(tot_time / 10) # 0.827902s

发现在我的机器上 10^7 数量级的计算在 10 次平均下是 0.827902 秒,接近一秒。

我们用搜索问题来举例

如果我们有一个有序数组 arr ,其中有 10^8 个数字,这时候给出一数字 n ,求在这个数组中是否有这个数 n ,有则返回 true 反之 false我们要求在 1000ms 时间内完成。

注意最后一句,如果我们采取枚举的方案来解决这个问题,那么我们根据之前的经验来估算,需要 10^8 / 10^7 * 1s 也就是 10

由于是有序数组,那么我们来计算一下二分查找的复杂度:

设数组中有 N 个元素,我们一共需要查询k次,根据这两个条件我们来推导一个 KN的通项公式(这里面,右边的式子代表在查询完k 次之后,剩余的元素个数)

由于 k 是查询的次数,也就是计算机一次运算的次数,所以我们只需要反解出 k 的值,也就是我们要求解的时间复杂度。我们假设第 k 次查询是最终态,那么说明此时剩余元素只有 1 个了。那么对于最终态的递推式就可以这样描述:

计算完了发展度之后,我们将 N = 10^7 带入,发现 k = 26.57542也就是说,只需要 27 次上下的计算机运算,也就是 27 / 10^7 约是 0.0000027 秒,就可以完成查询。

所以我们如此分析,通过上限时间来推断大致的算法复杂度,获得提示确定了思路,就可以开始解题了。

土法三:取极限估算复杂度

比如说这种题目:

给你一个无续数组 arr ,其中包含 n 个元素 (1 ≤ n ≤ 10^8),在给你一个 k 保证 (1 ≤ k ≤ n)。让你求出这个数组中的第 k 大数。我们要求在 1000ms 时间内完成。

看完题目第一反映,我们对 arr 数组先做一次降序排序,然后输出 arr[k] 即可。

那么我们开始使用土法二来估算时间,如果我们进行一次排序,假如是快排,那么首先我们需要一个 O(NlogN) 的复杂度来完成。然后还有一次查询,由于通过数组下标直接访问,需要 O(1) 的一次查询。

n 的范围右边界带入式中,由于我们知道 NlogN > N ,所以根据上面的经验,我们肯定要花费 10s 以上的时间来处理。虽然我们的想法很好,是对数组做一个预处理,然后再进行其他的算法,但实际上,由于预处理的复杂度已经远远的超过了其他计算的复杂度,也就是说我们对于一个方案的复杂度考量,往往都是在一个含操作数 N 的代数式中,当 N 取无穷大时,求每个子式子的等价无穷大,然后取最大值作为整个程序的复杂度

拿这题为例:

可能这个还不是很明显,我们再举一个例子:

如果我们遇到这种表达式,我们要如何求解呢?我的土法是分成 2 部:

1. 观察后舍去差距较大的

首先,n1 这两个子式显然要比前面两个都小(或者说肯定比 nlogn 要小),我们把它舍去。

2. 不确定式两两使用求极限,判断等价性

例如我们得到的 f'(n) 无法判断,那么我就取出这里面两个子式来求等价性:

所以我们发现剩下的两个式子是等价无穷大的。我们得到整体的时间复杂度:

所以我们可以总结出来一个规律,子式选最大,就是我们要的时间复杂度。

总结

这篇文章我们讲了:

  • 如何结合题目的数据量来估算程序耗时,以及通过复杂度的估算来提示我们要选用什么算法;
  • 耗时和复杂度的关系,大概就是 10^7 为一秒;
  • 取极限来舍去较小的子式,留下的最大子式即可作为整体算法的时间复杂度;

以上文章来源于让技术一瓜共食,作者冬瓜争做全栈瓜

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-11-27,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员维他命 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
看动画轻松理解时间复杂度(二)
上篇文章讲述了与复杂度有关的大 O 表示法和常见的时间复杂度量级,这篇文章来讲讲另外几种复杂度: 递归算法的时间复杂度(recursive algorithm time complexity),最好情况时间复杂度(best case time complexity)、最坏情况时间复杂度(worst case time complexity)、平均时间复杂度(average case time complexity)和均摊时间复杂度(amortized time complexity)。
五分钟学算法
2018/12/25
6530
客户端基本不用的算法系列:RMQ问题 - ST 算法
今天的算法可能有点难,但是如果我们只需要会使用 RMQ 问题的 ST 算法模板,这种程度就已经可以了!因为 RMQ 问题除了最优解的 ST 算法,剩下的都是高级数据结构的应用,例如:线段树、树状数组、Splay、Treap 甚至是主席树(额,我什么都没有暗示,业界就是这个名字)。好了今天我们从两个角度来解决这个问题。ST 算法和线段树。当然如果你对高级数据结构感兴趣,我也会在以后的文章中更新这个系列。
用户2932962
2019/07/17
1.1K0
算法(一)时间复杂度
前言 算法很重要,但是一般情况下做移动开发并不经常用到,所以很多同学早就将算法打了个大礼包送还给了老师了,况且很多同学并没有学习过算法。这个系列就让对算法头疼的同学能快速的掌握基本的算法。过年放假阶段玩了会游戏NBA2K17的生涯模式,没有比赛的日子也都是训练,而且这些训练都是自发的,没有人逼你,从早上练到晚上,属性也不涨,但是如果日积月累,不训练和训练的人的属性值就会产生较大差距。这个突然让我意识到了现实世界,要想成为一个球星(技术大牛)那就需要日积月累的刻意训练,索性放下游戏,接着写文章吧。 1.算法的
用户1269200
2018/02/01
8740
算法(一)时间复杂度
前端学数据结构与算法(一):不会复杂度分析,算法等于白学
兜兜转转了这么久,数据结构与算法始终是逃不过命题。曾几何时,前端学习数据结构与算法,想必会被认为不务正业,但现今想必大家已有耳闻与经历,面试遇到链表、树、爬楼梯、三数之和等题目已经屡见不鲜。想进靠谱大厂算法与数据结构应该不止是提上日程那么简单,可能现在已经是迫在眉睫。这次决定再写一个系列也只是作为我这段时间的学习报告,也不绝对不会再像我之前的vue原理解析那般断更了,欢迎大家监督~
飞跃疯人院
2020/10/07
9530
客户端基本不用的算法系列:快速幂
幂运算是我们平时写代码的时候最常用的运算之一。根据幂运算的定义我们可以知道,如果我们要求 x 的 N 次幂,那么想当然的就会写出一个 N 次的循环,然后累乘得到结果。所以我们要求幂运算的复杂度仍旧是
用户2932962
2019/08/28
5950
客户端基本不用的算法系列:快速幂
客户端基本不用的算法系列:Tarjan 算法的思路
在之前的 《客户端基本不用的算法系列:从 floodfill 到图的连通性》一文中,我们已经了解了在无向图中的割点和桥的定义。
用户2932962
2019/07/19
1.2K0
算法—时间复杂度[通俗易懂]
时间和空间都是计算机资源的重要体现,而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少;
全栈程序员站长
2022/08/27
3.3K0
算法—时间复杂度[通俗易懂]
前端轻松学算法:时间复杂度
相信认真阅读过本文,面对一些常见的算法复杂度分析,一定会游刃有余,轻松搞定。文章中举的例子,也尽量去贴近常见场景,难度递增。
用户1741436
2019/05/10
5470
前端轻松学算法:时间复杂度
解惑3:时间频度,算法时间复杂度[通俗易懂]
要理解时间复杂度,需要先理解时间频度,而时间频度简单的说,就是算法中语句的执行次数。
全栈程序员站长
2022/09/23
8650
解惑3:时间频度,算法时间复杂度[通俗易懂]
算法时间复杂度计算方式
【对于一个给定的算法,通常要评估其正确性和运行效率的高低。算法的正确性评估不在本文范围之内,本文主要讨论从算法的时间复杂度特性去评估算法的优劣。】
全栈程序员站长
2022/08/28
5460
算法时间复杂度计算方式
【初阶数据结构】——时间复杂度和空间复杂度详解(C描述)
我们已经了解了什么是算法,那当我们写出一个算法的时候,如何去衡量这个算法的好坏呢?
YIN_尹
2024/01/23
4360
【初阶数据结构】——时间复杂度和空间复杂度详解(C描述)
算法的时间复杂度和空间复杂度计算
在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n)= O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称为时间复杂度,是一种“渐进表示法”。其中f(n)是问题规模n的某个函数。
全栈程序员站长
2022/08/28
3.5K0
算法的时间复杂度和空间复杂度计算
什么情况下不能使用最坏情况评估算法的复杂度?
上一节,我们从最坏、平均、最好三种情况分析了算法的复杂度,得出结论,通常来说,使用最坏情况来评估算法的复杂度完全够用了。
彤哥
2020/07/23
6080
“算法复杂度”其实并没有那么复杂
算法是用于解决特定问题的一系列的执行步骤。使用不同算法,解决同一个问题,效率可能相差非常大。为了对算法的好坏进行评价,我们引入 “算法复杂度” 的概念。
程序员小猿
2021/01/19
3320
“算法复杂度”其实并没有那么复杂
时间复杂度与空间复杂度
在计算机程序编写前,依据统计方法对算法进行估算,经过总结,我们发现一个高级语言编写的程序程序在计算机上运行所消耗的时间取决于下列因素:
Rochester
2020/09/01
6700
【算法与数据结构】复杂度深度解析(超详解)
算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。
学习起来吧
2024/02/29
2870
【算法与数据结构】复杂度深度解析(超详解)
【数据结构】算法的空间复杂度
算法的时间复杂度和空间复杂度是度量算法好坏的两个重要量度,在实际写代码的过程中,我们完全可以用空间来换时间,比如说,我们要判断某某年是不是闰年,大家可能第一时间想到的都是写一个算法来判断每次输入的年份符不符合闰年的条件.但其实还有种方法是,我们可以事先建立一个有2050个元素的数组(年数比现实略多一点),然后把所有年份按下标数字对应,如果是闰年,此数组项的值设为1,否则设为0.这样,判断某年是否是闰年,就只需要查找一下对应数组项的值就可以了.这样求闰年的时间复杂度为O(1).既然空间复杂度这么好用,接下来我们就来一起学习它的基本内容吧.
修修修也
2024/04/01
1630
【数据结构】算法的空间复杂度
客户端基本不用的算法系列:素数筛法
今天的内容实用而且简单!素数问题是从来都是数学家热衷探索的领域,也是程序设计竞赛和 LC 中,解决数论相关问题的基础,下面本文介绍如何更科学地筛素数和一些相关的小知识。
用户2932962
2019/12/22
1.8K0
数据结构——复杂度
没有⼀种单⼀的数据结构对所有⽤途都有⽤,所以我们要学各式各样的数据结构, 如:线性表、树、图、哈希等。
用户11352420
2024/11/07
1270
数据结构——复杂度
一文搞懂算法的时间复杂度与空间复杂度
本文介绍了算法的时间复杂度和空间复杂度,包括基本概念、计算方法以及常见的时间和空间复杂度。同时,对于复杂情况,还分析了其时间复杂度和空间复杂度。
码科智能
2018/01/03
6.6K0
相关推荐
看动画轻松理解时间复杂度(二)
更多 >
交个朋友
加入腾讯云官网粉丝站
蹲全网底价单品 享第一手活动信息
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档