您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

从经典算法题看时间复杂度

时间:2020-03-11 14:36:55  来源:  作者:

本文首发公众号:架构精进,请移步,排版比较清晰。

经常有同学在 LeetCode 的题解中问解法的复杂度是多少。作为一个懒人,我一直在「逃避」这个问题,毕竟这东西听起来就这么「复杂」。

但本着对题解认真负责的态度(心虚),我想趁此机会做一个总结。下面我将通过一些较为经典的算法题聊一聊几种常见的时间复杂度。

什么是时间复杂度?

算法的时间复杂度(Time complexity)是一个函数,用于定性描述算法的运行时间。

提出时间复杂度的目的是:分析与比较完成同一个任务而设计的不同算法。

分析算法的结果意味着算法需要的资源,虽然有时我们关心像内存,通信带宽或者计算机硬件这类资源,但是通常我们想要度量的是计算时间。一般来说,通过分析求解某个问题的几种候选算法,我们可以选出一种最有效的算法。这种分析可能指出不止一个可行的候选算法,但是在这个过程中,我们往往可以抛弃几个较差的算法。 ——《算法导论》

大 O 符号

时间复杂度通常用 大 O 符号(Big O notation)表示。大 O 符号 又被称为渐近符号,是用于描述函数 渐近行为。

举个例子,假设我们解决一个规模为 n 的问题要花费的时间为 T(n)T(n):

T(n)=4n2−2n+2T(n)=4n2−2n+2

当 n 不断增大时,n2n2 开始占据主导地位,而其他各项可以被忽略,写作 T(n)=O(n2)T(n)=O(n2)。因此时间复杂度可被称为是 渐近 的。

常见复杂度比较

 

从经典算法题看时间复杂度

 

 

常见时间复杂度比较

常数时间

若算法 T(n)T(n) 的上界与输入大小无关,则称它具有常数时间,记作 T(n)=O(1)T(n)=O(1)。

常见的例子有:

  • 访问数组中的单个元素
  • 哈希表

别被循环所迷惑

例如这道题 有效的数独,需要在 9x9 的格子中判断数独是否有效。

思路:把行、列和小正方形区域出现的数字用哈希表记录下来,在遍历过程中只要判断数字是否在这三个范围出现过就行了,如果出现过就返回 False。

题解如下:

 

从经典算法题看时间复杂度

 

 

我们可以看到,虽然题解中用到了如下循环:

 

从经典算法题看时间复杂度

但由于复杂度始终是 O(9×9)O(9×9),加上使用哈希表来判断元素是否存在,所以算法的复杂度始为 O(1)O(1)。

对数时间

若 T(n)=O(logn)T(n)=O(logn),则称其具有对数时间。

常见例子:

  • 二叉树相关操作
  • 二分查找

为什么是 logn?

什么是对数?

首先,我们复习一下 对数。

对数 是幂运算的逆运算。假如 x=βyx=βy,那么就有 y=logβxy=logβx。其中:

  • ββ 是对数的底(基底)
  • yy 就是 xx(对于底数 ββ)的对数

那我们说一个算法的复杂度是 O(logn)O(logn),那么 lognlogn 这个对数的底数去哪了?

换底公式

二分查找

从经典算法题看时间复杂度

 

线性时间

如果一个算法的时间复杂度为 O(n)O(n),则称这个算法具有线性时间。随着样本数量的增加,复杂度也随之线性增加。常表现为单层循环。

来看一到例题 求众数。这里我们用了摩尔投票法,时间复杂度为 O(n)O(n)。

 

从经典算法题看时间复杂度

 

 

线性对数(准线性)时间

若算法复杂度为 T(n)=O(nlogn)T(n)=O(nlogn),则称这个算法具有线性对数时间。可以理解为执行了 n 次对数时间复杂度的操作。

有几种排序算法的平均时间复杂度都是线性对数时间,例如:

  • 堆排序:前 K 个高频元素
  • 快速排序:颜色分类
  • 归并排序

二次时间

若算法复杂度为 T(n)=O(n2)T(n)=O(n2),则称这个算法具有二次时间,即时间复杂度随着样本数量的增加呈平方数增长。常表现为双层循环。

常见的算法中有一写比较慢的排序算法,例如:

  • 冒泡排序
  • 选择排序
  • 插入排序

由于涉及的排序算法很多,若一一讲解的话就偏离这篇文章的侧重点了。如果大家对各类算法感兴趣可以参考:维基百科:排序算法。

算法是生活中的大智慧,而我们都是智慧的受益者。



Tags:算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Tags: 算法  点击:(1)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  Tags: 算法  点击:(7)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15  Tags: 算法  点击:(16)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  Tags: 算法  点击:(24)  评论:(0)  加入收藏
基于算法的业务或者说AI的应用在这几年发展得很快。但是,在实际应用的场景中,我们经常会遇到一些非常奇怪的偏差现象。例如,Facebook将黑人标记为灵长类动物、城市图像识别系统...【详细内容】
2021-11-08  Tags: 算法  点击:(32)  评论:(0)  加入收藏
随着注册制的加速推进,新股越来越多,截止到今天A股上市公司的总数高达4500余家,A股一直就是重融资,轻投资的市场,而上市公司发行可转债这种再融资的(圈钱方式)是最能让普通投资者接...【详细内容】
2021-11-05  Tags: 算法  点击:(98)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  Tags: 算法  点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  Tags: 算法  点击:(36)  评论:(0)  加入收藏
每个人都有过这样的经历:打开手机准备回消息或打电话,一看到微信图标右上方的小红点,于是忍不住先打开微信;看完微信,不知不觉又被另一个App牵引,直到关闭手机屏幕才发现自己早已...【详细内容】
2021-11-03  Tags: 算法  点击:(30)  评论:(0)  加入收藏
文丨互联网怪盗团在互联网行业,尤其是在投资人心目中,往往存在一种“算法迷信”或曰“技术迷信”:某公司的广告变现做得好,一定是因为有算法;某公司的云计算业务开展的好,也是因为...【详细内容】
2021-11-03  Tags: 算法  点击:(25)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条