并行可以降低计算复杂度？？ (转载) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

并行可以降低计算复杂度？？ (转载)

并行可以降低计算复杂度？？ (转载)# Joke - 肚皮舞运动

t*82015-05-04 07:05

1 楼

【以下文字转载自 PhotoGear 讨论区】
发信人: terry2008 (Terry), 信区: PhotoGear
标题: 大家如何给娃取名字
发信站: BBS 未名空间站 (Fri Jun 18 19:06:25 2010, 美东)
是纯拼音
还是来个英文名+拼音？

n*72015-05-04 07:05

2 楼

【以下文字转载自 Programming 讨论区】
发信人: nowhere7 (折腾), 信区: Programming
标题: 并行可以降低计算复杂度？？
发信站: BBS 未名空间站 (Mon May 4 17:53:30 2015, 美东)
最近看一篇文章，GPU计算的
用的deep learning
其中提到NN的计算复杂度是O(MN+LN^2)
M是输入的unit，N是所有layer的hidden unit，L是layer数
然后用GPU并行之后，就是M，N的linear时间复杂度了？
说原因是，计算两个N dimension vector的内积，用CPU是O(N)的，用GPU是O(1)
这是鬼扯吧？
我怀疑实际原因是，他们的GPU平台有近3K个core，计算中M在2000左右，N在几千数量级
所以他们是用core的数量K 抵消的一个N的复杂度
大家看是不是这样？

m*a2015-05-04 07:05

3 楼

没有规定吧，看你们自己家的定位了.

【在 t*******8 的大作中提到】

: 【以下文字转载自 PhotoGear 讨论区】
: 发信人: terry2008 (Terry), 信区: PhotoGear
: 标题: 大家如何给娃取名字
: 发信站: BBS 未名空间站 (Fri Jun 18 19:06:25 2010, 美东)
: 是纯拼音
: 还是来个英文名+拼音？

k*22015-05-04 07:05

4 楼

这是算法课没及格的说法吧。
并行再牛，也不能改变计算复杂度，因为计算复杂度是以N->无穷的极限情况来讨论的
。这种情况下任何有限的core都可以忽略不计。
唯一能改变计算复杂度的是发明一个新的更高效的算法。

【在 n******7 的大作中提到】

: 【以下文字转载自 Programming 讨论区】
: 发信人: nowhere7 (折腾), 信区: Programming
: 标题: 并行可以降低计算复杂度？？
: 发信站: BBS 未名空间站 (Mon May 4 17:53:30 2015, 美东)
: 最近看一篇文章，GPU计算的
: 用的deep learning
: 其中提到NN的计算复杂度是O(MN+LN^2)
: M是输入的unit，N是所有layer的hidden unit，L是layer数
: 然后用GPU并行之后，就是M，N的linear时间复杂度了？
: 说原因是，计算两个N dimension vector的内积，用CPU是O(N)的，用GPU是O(1)