每个开发者都必须知道的14个数字

Eremita

2013-04-02

Jeff Dean , 一位著名的 Google 工程师, 推出了一个每个人都必须知道的数字的潜在数字列表。这个列表对设计大型基础架构的系统是一个巨大的资源。

算法及其复杂性总是会在计算机系统的关键部分出现，但我发现很少有工程师对一个O(n!)级算法相较一个 O(n5) 算法会怎样有很好的理解。

在编码比赛世界里，竞争选手一直在考虑这些优化权衡。毫不奇怪，有一组每个算法设计者都应该知道的数字。

下面的表格显示了不同复杂度算法条件下，在几秒钟内它们可以达到的极限，n是输入量大小。我已经为每个复杂的类型增加了一些算法和数据结构的例子。

n最大值	复杂度	算法	数据结构
1,000,000,000 and higher	log n, sqrt n	对分查找，三元查找，快速指数，欧几里得算法
10,000,000	n, n log log n, n log* n	集合相交, Eratosthenes筛选法,基数排序, KMP算法,拓扑排序,欧拉路径, 强连通分量, 2sat图	不相交的集, tries树, 哈希映射, 滚动散列双端队列
1,000,000	n log n	排序, 分治法, 扫描线算法, Kruskal算法, Dijkstra算法	段树, 范围树, 堆, 二叉排序树, 树状数组, 后缀数组
100,000	n log² n	分治法	2d范围树
50,000	n^1.585, n sqrt n	Karatsuba乘法算法, 平方根技巧	两层树
1000 - 10,000	n²	最大空矩形, Dijkstra算法, 普里姆算法 (密集图)
300-500	n³	所有对最短路径, 最大和子阵,原生矩阵乘法, 矩阵链乘积, 高斯消元法, 网络流
30-50	n⁴, n⁵, n⁶
25 - 40	3^n/2, 2^n/2

Eremita

0 关注 0 粉丝 0 动态

相关推荐

MySQL ddl语句的使用

数据定义语言create、drop、alter语句。定义对数据库记录的增、删、改操作。定义对数据库、表、字段、用户的访问权限和安全级别。这小节主要了解下数据定义语言DDL。我们用它对数据库、表进行一些管理操作，比如：建库、删库、建表、修改表、删除表、对字

云中舞步 2020-11-12

MySQL全面瓦解之查询的正则匹配详解

上一章查询的过滤条件，我们了解了MySQL可以通过 like % 通配符来进行模糊匹配。同样的，它也支持其他正则表达式的匹配，我们在MySQL中使用 REGEXP 操作符来进行正则表达式匹配。似，但又强大很多，能够实现一些很特殊的、复杂的规则匹配。如果

杨德龙 2020-11-11

shell中set指令的用法详解

set 指令可根据不同的需求来设置当前所使用 shell 的执行方式，同时也可以用来设置或显示 shell 变量的值。当指定某个单一的选项时将设置 shell 的常用特性，如果在选项后使用 -o 参数将打开特殊特性，若是 +o 将关闭相应的特殊特性。而不带

JohnYork 2020-10-16

详解shell 函数定义与调用

本节程序实现函数定义与调用，注意调用函数是不要使用括号，代码如下：。本节程序实现向被调用函数传递参数，$0是运行该脚本的shell传递的参数从$1开始、传递多个参数是以空格分隔，代码如下：。与$*相同，但是使用时加引号，并在引号中返回每个参数。显示Shel

wangzhaotongalex 2020-09-22

Python list和str互转的实现示例

输出： [1, 2, 3, 4, 5]. list2 = str2.split() #or list2 = str2.split(" "). 以下几个内置的函数可以执行数据类型之间的转换。这些函数返回一个新的对象，表示转换的值。将x转换

xiaoseyihe 2020-11-16

MongoDB查询之高级操作详解（多条件查询、正则匹配查询等）

MongoDB查询文档使用find()方法，同时find()方法以非结构化的方式来显示所有查询到的文档。db.collection.find -- 返回所有符合查询条件的文档。$type操作符是基于BSON类型来检索集合中匹配的数据类型，MongoDB中可

不要皱眉 2020-10-14

PHP如何通过date() 函数格式化显示时间

n 为无前导0数字月份。月份中的第几天，前面有前导0，如03。date; //显示格式如 2008-12-01 12:01. 如果输出的时间和实际时间差8个小时的话，检查php.ini文件，做如下设置：date.timezone = PRC

Crazyshark 2020-11-13

ThinkPHP5分页paginate代码实例解析

$list = db('user')->paginate(10);$list = db('user')->paginate(10,false,['query'=>array('id' => $id)]);$this->assi

K先生 2020-11-10

jQuery实现日历效果

jquery是用的是2.0版本。--基于W3C标准不用做任何修改-->. --设置初始化文档信息和文档管理标注-->. --整个页面编码 utf-8 国际编码通用性最强，GBK/gb2312 中文-->. .signincalenda

momode 2020-09-11

程序员你是怎么绘制架构图？

作为一个程序员，假如让你绘制当前正在开发的项目的架构图，你会怎么绘制？先来同步一个理念。一种架构设计的方法论，忽略不在同一个抽象成绩的细节，从而可以更好的表达和可视化。可以类比地图，地图分4个级别，国家，省，市，街道；而C4模型也分4个层级，Context

思君夜未眠 2020-09-04

聊一聊mycat数据库集群系列之双主双重实现

　　最近在梳理数据库集群的相关操作，现在花点时间整理一下关于mysql数据库集群的操作总结，恰好你又在看这一块，供一份参考。本次系列终结大概包括以下内容：多数据库安装、mycat部署安装、数据库之读写分离主从复制、数据库之双主多重、数据库分库分表。我是一个

点滴技术生活 2020-08-21

C# 正则表达式

.Net 框架提供了允许这种匹配的正则表达式引擎。模式由一个或多个字符、运算符和结构组成。正则表达式中的反斜杠字符（\）指示其后跟的字符是特殊字符，或应按原义解释该字符。与报警符 \u0007 匹配。" + ‘\u0007‘ 中的 "

MaggieRose 2020-08-19

Python基础---转义字符——Python

字符串中的转义字符。\t 在控制台输出一个制表符，协助在输出文本时垂直方向保持对齐。制表符的功能是在不使用表格的情况下在垂直方向按列对齐文本

kevinweijc 2020-08-18

HikariCP => 现阶段最快的数据库连接池

怎么说.... 有图有真相吧~要知道对于连接池来讲,代码越少,占用cpu和内存越少,Bug出现几率也是越小,那么代表他的执行率高,这就是为什么HikariCP受欢迎的原因之一。HikariCP是经受了市场的考验,走过太上老君的丹炉,现如今拿到SpringB

wintershii 2020-08-17

Redis 执行性能测试

Redis 性能测试是通过同时执行多个命令实现的。仅运行以逗号分隔的测试命令列表。仅打开 N 个 idle 连接并等待。$ redis-benchmark -h 127.0.0.1 -p 6379 -t set,lpush -n 10000 -q. 以上实

vapaad 2020-08-17

Redis服务之高可用组件sentinel详解

有没有这样的一组件帮我们对master做实时的监控，一旦发现master宕机就提升一个slave当选新的master，如果原master还有其他slave，将其他slave都从属于新的master；除此之外它还应该让系统在发生切换master时触发报警通知

wera00 2020-08-17

js实现表格单列按字母排序

本文实例为大家分享了js实现表格单列按字母排序的具体代码，供大家参考，具体内容如下。<link href="../css/表格数据搜索.css" rel="stylesheet">. <input

移动开发与培训 2020-08-16

js实现表格数据搜索

<input type="text" placeholder="搜索..." id="myInput" onkeyup="myFunction()">

ReunionIsland 2020-08-16

PyQt5 QDockWidget控件应用详解

QDockWidget是一个可以停靠在QMainWindow内的窗口控件，它可以保持在浮动状态或者在指定位置作为子窗口附加到主窗口中，QMainWindow类的主窗口对象保留有一个用于停靠窗口的区域，这个区域在控件的中央周围。QDoCKWidget类中的常

JimyFengqi 2020-08-16

使用imp和exp命令对Oracle数据库进行导入导出操作详解

例子：导出mydb数据库system用户，密码为123456的所有数据到D:\example.dmp文件中

love0u 2020-08-16

Eremita

W3CSchool教程: HTML 教程; CSS 教程; Bootstrap 教程; Javascript 教程; jQuery 教程

后端教程: C 教程; Java 教程; PHP 教程; Python 教程; Go 教程

移动开发: Android 教程; Swift 教程; Kotlin 教程; jQuery Mobile 教程; ionic 教程

关于我们: 新闻动态; 联系方式; 招聘英才; 安科实验室; 帮助与反馈

安科网(Ancii)，中国第一极客网

Copyright © 2013 - 2019 Ancii.com

京ICP备18063983号京公网安备11010802014868号