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

2017-07-29 01:22:27 +08:00
 qq12345454

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

5236 次点击
所在节点    问与答
19 条回复
fuermosi777
2017-07-29 01:27:46 +08:00
算法 4
lydasia
2017-07-29 01:34:04 +08:00
算法复杂度
weyou
2017-07-29 01:44:00 +08:00
买高中数学书就可以了
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
MCVector
2017-07-29 04:14:29 +08:00
可以理解为计算时间是问题规模的函数。这个函数是个多项式,而且最高次幂是 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
抽象概念,复杂度。
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
通俗理解即:是衡量算法快慢的一个指标

所有算法都能得出这个时间复杂度,解决相同问题的不同算法的优劣,一般是根据时间复杂度衡量。
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)

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/378750

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX