作者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