前幾天我在jobstreet看到有趣的東東

faiko

回复 14# Squall_Chua 的帖子
就算是parallel algorithm也是由无数的sequential algo组成的。呵呵……

你的O(N^2)，我有异议。应该是O(N)罢了

Prime number test algorithm，网路上很多……自己慢慢研究 你说的test到sqrt(N)应该是 Sieve of Eratosthenes...还有其他的方法，懒惰去研究

在下是research student……不过，不是在algorithm study那方面。parallel processing element design是我的范围内。嗯……tree searching algorithm 是我的研究范围 这个才是O(N^2)甚至可以是O(EXP^N)的。

回复 18# 晨天 的帖子
这个要看compiler 和 library

可以参考Intel TBB (Thread Building Block)....不过，通常简单的用法就是create process thread...让OS/Virtual Machine来分配processing resource。

回复 20# Squall_Chua 的帖子
没有利害，只是玩玩罢了。
Parallel processing可以很简单，也可以很难。范围也不小。

P/S:这间公司是做telco的，有机会可以去试试看。

Squall_Chua

那個O(N^2)我覺得應該沒錯啦
雖然我不是很會mathematical proof
N個數目裡面有N/2個odd number吧
這個是跑不掉了的
然後每一個數目都要check是不是prime
所以total operation應該有
1 + 2 + 3 + 4 + ... + N/2 = (N/2 + 1) * (N/4) = (2N^2 + 4N) / 16 = (N^2 + 2N) / 8
所以應該是O(N^2)吧

(懶惰拿紙出來算,不懂有沒有算錯)


thread building block我有看過
不過是GPL的
在commercial上面可能沒那麼實際

我正在學的是mpi
然後有學校的三台grid server來玩

科技小女孩

原帖由 Squall_Chua 于 28-2-2009 10:38 PM 发表 algorithm簡單來說就是一個step by step的instruction來解決一個問題wiki應該會解釋到比較清楚http://en.wikipedia.org/wiki/Algorithm至於prime number的話你中學時期應該有學過就是除了1之外,只能夠給自 ...

哦！记得了，algorithm是用c/c++来写的对吗？ 我还有读，pointer, array, link, link list这些的哦

Squall_Chua

algorithm是在任何language上面都能使用的
不一定是C/C++

科技小女孩

原帖由 Squall_Chua 于 1-3-2009 10:30 AM 发表 algorithm是在任何language上面都能使用的不一定是C/C++

哦，哎呀，我学的东西不多。惭愧哦！
却在这里一直问。不好意思哦！

faiko

回复 22# Squall_Chua 的帖子
你的algo本身有问题。

Prime number test & Find Prime Number是不同的。两者的complexity是不同的。所以，Find Prime Number应该是1+1+1+1+N个1。

Prime number test是说，给你一个号码。你去找它是否是个质数（Prime number）。你必须从每个prime来factorize它，去test。

Find prime number，是去寻找prime number。因为，你找到了1st prime，跟着下去其倍数可以不用去test了。这也是sieve of eratosthenes的concept。

不过我太久没有去动algorithm complexity的东西了。当年也不过是一个subject罢了

回复 25# 科技小女孩 的帖子
知道自己的不足，就要不断努力去增加自己知识 学校学的，永远都不比外面来得多的。

在C Language里面，去学 Pointer/ Function Pointer，这两个在industry里面是很重要的东西，也是为什么C还不会死掉。

Java, C, C++ 在不同的industry level，有不同的功用。除了会algorithm + logical thinking以外，必须懂得抓住每个程序语言的特性，这样才可以完全发挥它们的功用

科技小女孩

pointer 和 function， 我只是学到简单的。我想问我们读IT的，有什么不懂，在google 找到的吗？

Squall_Chua

我是拿你開始說的那個只check odd number的algorithm
然後來算出解決那個問題的complexity
這個不是在算sieve的啦
簡單來說就是把尋找prime number和test prime number的algorithm算在一起
就是整個問題的complexity啦


同樣的東西放在那裡
結果被shoot


[ 本帖最后由 Squall_Chua 于 1-3-2009 02:57 PM 编辑 ]

faiko

回复 27# 科技小女孩 的帖子
pointer & functor (function pointer)
Google可以找到你要的东西。但是，你学到里面的知识吗？

P/S:我不是IT的 我是EE grad的

回复 28# Squall_Chua 的帖子
呵呵……就算你对吧。我说的方法不需要用到prime test的。看你怎样去solve罢了。

其实，不用太在意。这些东西在不同地方，不同反应。

老实说，这个公司的用意也不过是看应征者如何写code （design effective data structure, implement algorithm)。其实，google一下。就很多example了，但是，懂得如何运用，却是另外一回事 只是会copy n paste coding不代表你会。这种staff，绝对做不上technical leader的，就算做到，也会给厉害的人拉下。

科技小女孩

什么是EE GRAD？
我要的东西，大多数没有咯！
可是在书里可以找到哦

晨天

他的意思是 他是一名 engineering graduate
哪一系的？？？
electronic？?

＠Squall_Chua
prime number test 有时候一开头就中， 有时候最后一个才中
可是complexity 都是一样。。。。。。。

faiko

回复 30# 科技小女孩 的帖子
EE Grad = Electronic/Electrical Engineering Graduate
你不会找罢了。就算是课本，用google可以找到 不过是犯法的
而且，你会的话，可以通过google来找别间大学的lec notes, tutorial等等。看你有没有心罢了。不过，我就没这么做。懒惰

回复 31# 晨天 的帖子
electronic majoring telecommunication
不过现在集中火力于semantic web, logic reasoning有关的东西。跟comp science有关，不过偏向于applied engineering这里。
有点难度 快断气了

Squall_Chua

我懂你說的那個algorithm啊
只是解釋一下用brute force的話有多慢而已
要記得有新手進來這裡


我看到那個人這種回復後
我就不想理他了
繼續回復下去只是永無止盡的吵下去而已
也許是我沒把我要討論的point說清楚吧

Squall_Chua

算Big O complexity的時候當然是算worse case的啦
所以都差不多的

科技小女孩

哦，原来是这样的.谢谢你faiko，因为我真的不知道能这样的
哎~亏我还是读IT的，失败。不过还是谢谢你噢`

科技小女孩

哦。。engineering的
原来如此

cristiano~7

我想樓主想表達的O(n ^ 2)是指整個問題的時間複雜度吧
因爲樓主的做法是n個號碼，每一個號碼去測試是否質數
因爲loop n 次加上測試某個號碼是否質數是O(n)複雜度
所以樓主解決整個問題需要O(n ^ 2)的時間複雜度

有一點需要更正的地方，就是樓主解決問題的方法並非是O(n ^ 2)
先讓大家想想看問題出在那裏，之後我再解析爲什麽不是O(n ^ 2)

其實我並不排除可能O(n)内就可以解決這個問題，就像faiko提出的方法
等我今晚有空后再算算不同方法的複雜度

vampcheah

原帖由 faiko 于 1-3-2009 12:27 PM 发表
Prime number test是说，给你一个号码。你去找它是否是个质数（Prime number）。你必须从每个prime来factorize它，去test。

Find prime number，是去寻找prime number。因为，你找到了1st prime，跟着下去其倍数可以不用去test了。这也是sieve of eratosthenes的concept。

这点我很认同。只要之前的prime number 都不能 factorize 的话就已经证实号码本身就是一个 prime number
所以 O（n/2）这个处理速度应该会比较慢。处理时，只要把之前出现过的 prime number 测试一下就知道了。

相信这个题目不止algo 方面吧，如何处理整个program 也是重点之一。
使用recursive 的应该会比较吃香

虽然我已经转去网页编程但是基本的algo 应该是一样的。

faiko 的理论很强哟。什么 sieve of eratosthenes 我都不会 （还了给lecturer）

[ 本帖最后由 vampcheah 于 2-3-2009 04:48 PM 编辑 ]

晨天

原帖由 cristiano~7 于 2-3-2009 11:31 AM 发表
我想樓主想表達的O(n ^ 2)是指整個問題的時間複雜度吧
因爲樓主的做法是n個號碼，每一個號碼去測試是否質數
因爲loop n 次加上測試某個號碼是否質數是O(n)複雜度
所以樓主解決整個問題需要O(n ^ 2)的時間複雜度
...

我等待答案

原帖由 vampcheah 于 2-3-2009 04:47 PM 发表

这点我很认同。只要之前的prime number 都不能 factorize 的话就已经证实号码本身就是一个 prime number
所以 O（n/2）这个处理速度应该会比较慢。处理时，只要把之前出现过的 prime number 测试一下就知道了。
...

recursive 不会浪费memory 吗？？？

sieve of eratosthenes 一经过时了
新的algo 是 sieve of atkin

是运用number theory的concept

Squall_Chua

有醬的algorithm的啊
那個number theory好像有點難下
懶惰去看