在一个n位数组中找最小值的复杂度到底是多少 - Computation版 - 未名存档

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

Computation版 - 在一个n位数组中找最小值的复杂度到底是多少

相关主题
● 菜鸟急问：两个数组相加，复杂度是否可以降到O(1)	● 贡献一个问题
● MPICH2并行程序配置内存空间问题	● 终于完成一模拟matlab基本矩阵运算的C库
● c++为什么比c慢？	● Re: [转载] any procedures to compute and show the permutations?
● [转载] 求最小值的问题，多谢	● 有lsf queue大牛么
● 请问寻找最小值的问题	● [转载] 大家看这个方程组用什么软件解
● 如何找出集合中的最小值	● 请教关于matlab benchmark
● An interview question: how to sort a very long list?	● 并行的算法
● 有人用 Macsyma 作符号运算吗？	● 大家作并行计算的时候都是怎么作load balancing的？

相关话题的讨论汇总
话题: 复杂度话题: 中找话题: 最小值

进入Computation版参与讨论

1

(共1页)

c*******n
发帖数: 112

1

如体，
看到很多Paper上都说是O(log n)。但是我认为是O(n)。原因如下：
如果有计算机可以并行处理，当然我们可以认为运算时间是O(log n)。而实际上
总的比较次数还是n次，因此算法复杂度仍然是O(n)

1

(共1页)

进入Computation版参与讨论

相关主题
● 大家作并行计算的时候都是怎么作load balancing的？	● 请问寻找最小值的问题
● 请教各位大下， MPI并行计算的问题	● 如何找出集合中的最小值
● 谁推荐个测PC的浮点运算速度的程序?多谢	● An interview question: how to sort a very long list?
● Re: [转载] Re: 做计算买什么样的机器最好？	● 有人用 Macsyma 作符号运算吗？
● 菜鸟急问：两个数组相加，复杂度是否可以降到O(1)	● 贡献一个问题
● MPICH2并行程序配置内存空间问题	● 终于完成一模拟matlab基本矩阵运算的C库
● c++为什么比c慢？	● Re: [转载] any procedures to compute and show the permutations?
● [转载] 求最小值的问题，多谢	● 有lsf queue大牛么

相关话题的讨论汇总
话题: 复杂度话题: 中找话题: 最小值

未名新帖统计// 7月16日

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)