作者yauhh (喲)
看板CSSE
標題Re: [問題] 未排序的陣列，演算法相關問題
時間Mon May 10 00:22:20 2010
※ 引述《dryman (dryman)》之銘言：
: 用Perl隨便兜一個
: 雖然這不能當演算法的解答啦
: 不過就應用上還蠻不錯的XD
: @x = 1..60;
: @y = 30..100;
: $num = 50;
:
: @xhash{@x}=0..$#x;
: @yhash{@y}=0..$#y;
:
: foreach $item (@x) {
: push @pair,[$xhash{$item},$yhash{$num-$item}] if exists $yhash{$num-$item};
: }
看你這一段程式有些小小疑惑,就當做hash真強到找什麼都O(1)好了,
先考慮一種情況:
首先把X,Y陣列的值都丟到xhash和yhash,
你找到一個$xhash{$item},$item表示X陣列的一格值,所以用$num-$item找yhash,
找到Y陣列中的另一格值$yhash{$num-$item}.
接下來有個問題是:$yhash{$num-$item}是Y的第幾格?
在這個情況中,看起來沒有處理這個... 而是否沒處理這個讓你得到O(n)的印象?
考慮另一種情況:
也許我不懂perl,把它看錯了,其實是把X,Y陣列的每一格,包含{index,value}都丟進
hash. 所以$xhash{$item}是{i,v}這樣的內容,把它拿去yhash找的時候,
一定要做兩個動作:
1. 把v取出找$num-v
2. 在yhash找到合適的{j,$num-v}.
然後你才可以找到一對(i,j),其X[i]與Y[j]總和為$num.
在這種情況中,找到對應的{j,$num-v}顯然不會是O(1)的,假設有k個這種j,
就要找j次. 這樣算總數起碼也是個O(m*k),m是X長度,k可視同為Y長度.
是哪種情況呢?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.109.178