O(N^2) 请问这个公式是什么意思，我只上过小学

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 2664 天前的主题，其中的信息可能已经有所发展或是发生改变。

好像和冒泡有关，面对这些乱七八糟的数字字母公式，请问我应该买什么书回来学习

第 1 条附言 · 2017-07-29 11:07:55 +08:00

感谢所有回复的朋友

你们说的线性、极限语言、微积分这些词汇，基本从来都没有听过

看来我一定要好好学习

公式

请问

冒泡

乱七八糟

19 条回复 • 2017-07-29 12:58:39 +08:00

fuermosi777

2017-07-29 01:27:46 +08:00

算法 4

lydasia

2017-07-29 01:34:04 +08:00 via iPhone

算法复杂度

weyou

2017-07-29 01:44:00 +08:00 via Android

买高中数学书就可以了

xupefei

2017-07-29 01:59:47 +08:00

指的是如果输入数据的量是 n，这个算法需要进行 n 平方次的运算。注意这里指的不是算法的运行时间。
这叫 Big O notation。

xupefei

2017-07-29 02:00:44 +08:00

@xupefei 其实“需要进行 n 平方次的运算”也不太对，这里的平方只是一个度，并不是具体的量。

crab

2017-07-29 02:03:26 +08:00

http://www.ehcoo.com/complexity.html#Big-O-notation

MCVector

2017-07-29 04:14:29 +08:00 via Android

可以理解为计算时间是问题规模的函数。这个函数是个多项式，而且最高次幂是 2。

Andiry

2017-07-29 04:40:33 +08:00

用小学生的语言来讲：
排序一个十个数的数组，可能要做一百次运算；
排序一个一百个数的数组，可能要做一万次运算；
依此类推

starvedcat

2017-07-29 06:04:05 +08:00

不需要买书，上网看文章就行
搜索“时间复杂度”

skadi

2017-07-29 08:58:26 +08:00

O 渐近时间复杂度.
就是说这个算法的时间复杂度是输入 N 的平方.
po 大概需要一本算法导论进阶.

zander

2017-07-29 09:11:27 +08:00 via Android

抽象概念，复杂度。

kindjeff

2017-07-29 10:21:31 +08:00

只上过小学太困难了吧，至少还得看初中和高中数学呀

ipwx

2017-07-29 10:27:06 +08:00

严格的大 O 定义要用极限语言，有微积分基础才行。

所以楼主别追求严格定义了，形象理解一下就行。就是这个算法消耗的时间和你的数据量成平方相关，系数不确定。但是常数系数一般在算法复杂度分析里面忽略。

复杂度分析理论的优势是，不需要跑一下程序，就可以估计算法之间的优劣。

lzjamao

2017-07-29 10:31:31 +08:00

x 与 y 的关系趋势。

lzjamao

2017-07-29 10:33:12 +08:00

@lzjamao
1.线性关系。如 x 增加 1，y 增加 1，y = x + 1。放大 2 倍，y 也放大 2 倍。y = x * 2
2.非线性关系。如 x 增加 1，x^2 + y ^ 2 = 1 （ x 的 2 的平方根），x 为正数或负数减时。y 都有两种结果

zyqf

2017-07-29 10:52:09 +08:00 via Android

通俗理解即：是衡量算法快慢的一个指标

所有算法都能得出这个时间复杂度，解决相同问题的不同算法的优劣，一般是根据时间复杂度衡量。

geelaw

2017-07-29 12:44:41 +08:00

@crab #6 这篇文章非常糟糕，最开始对 O 的定义就有问题。

ic2y

2017-07-29 12:51:48 +08:00

买本《数据结构与算法》研究研究吧，先不要买《算法导论》《算法分析》这种巨难的书

ovear

2017-07-29 12:58:39 +08:00

LS 说的好复杂。。
语句频度中，最高的数量级。。

语句频度：一条语句执行的次数

for(int i = 0; i<n; i++){
do(); //语句频度 n
}

for(int i = 0; i<n; i++){
sout("a");//语句频度 n
for(int j = 0; j<n; j++){
do();//语句频度 n^2
}
}

语句频度之和 n^2 + n
算法复杂度 O(n^2)