<UPDATE>
说明，由于数据规模是 n*m, 所以复杂度是 O(log(n) * log(m*n))；不妨设 n >= m，则 O(log(m*n)) = O(log(n*n)) = O(2*log(n)) = O(log(n)) —— 突然想到 m 时我还以为自己错了呢，其实没错，诶。
</UPDATE>
正在长大的忆向童鞋某次讨论了关于判断 Young 氏矩阵 中元素存在性的问题，当时我就觉得可以在 O(log(n)) 时间内得出结论——后来发现错了，但 O(log(n)^2) 也还是够了。
先抄一段关于 Young 氏矩阵的介绍，介绍得不好别怪我因为不是我写的。
一个 m*n 的 Young 氏矩阵(Young tableau) 是一个 m*n 的矩阵, 其中每一行的数据都从左到右升序, 每一列的数据都从上到下升序. 所以, Young 氏矩阵可以用来存放 r<= mn 个有限的元素.
我们要做的事情是，在一个 Young 氏矩阵中找出某个值的位置，或者判断它是否存在。
搜了一下，发现还真没有谁提出可以用亚线性的时间复杂度完成这样的工作。
为了证明俺是对的，我把代码给码出来了，然后实际操作了一下，先看结果：
横坐标：矩阵规模（为了方便画图，这里用的是 n x n 矩阵）
纵坐标：比较次数
红线：直线 y = x
绿线：实际“有效”的比较次数
蓝线：加上参数合法检验等判断在内总共的比较次数
说下思路：在对角线上面找出和要找的数（设为 x 吧）最接近且小于等于 x 的一个值，如果这个值不等于x，那么可以这个值为界，丢掉包括它在内的左上角和不包括它的右下角，原因很显然嘛——然后递归在剩下的部分中找就是了。
——于是一次能丢掉 1/2 左右的数据。
上面在对角线上寻找最接近值的过程又可以用二分法以 O(log(n)) 复杂度得到。
于是总体复杂度就是 O(log(n)*log(n)) = O(log(n)^2) 了。
简单拟合了一下， 绿线： 5 ln(n)^2，紫线： 15 ln(n)^2 —— 多么和谐啊！
代码如下，感兴趣的拿去玩吧，版权还没没想好。
from numpy import *
from random import *
def genRandomYoung( rows, cols ):
y = zeros( (rows, cols), int );
t = randrange( 0, 10 );
for c in range( cols ):
t = y[0][c] = randrange( t, t+10 );
for r in range( 1, rows ):
t = y[r-1][0];
for c in range( cols ):
if t < y[r-1][c]:
t = y[r-1][c];
t = y[r][c] = randrange( t, t+10 );
#print(y);
return y;
def mySuperBinarySearch( young, rect, what ):
x = rect['x'];
y = rect['y'];
rows = rect['rows'];
cols = rect['cols'];
if rows==0 or cols==0:
return None;
k = (cols+0.0)/(rows+0.0);
pos = lambda n: (int(y+n), int(x+n*k));
if (k > 1):
pos = lambda n: (int(y+n/k), int(x+n));
get = lambda p: young[p[0]][p[1]];
n = rows if k<1 else cols;
if n==1 and get(pos(0)) != what:
return None;
#for i in range(n):
# print( get(pos(i)) )
f = 0;
b = n;
m = 0;
m2 = -1;
while m != m2:
m2 = m;
w = get(pos(m))
if( what < w ):
b = m;
elif( what > w ):
f = m;
else:
return pos(m);
m = (f+b)/2;
m = (f+b)/2;
if( get(pos(m)) > what and m>0):
m = m-1;
p = pos(m);
w = get(p);
if( w == what ):
return p;
rect = {'x': x, 'y': p[0]+1, 'rows': y+rows-p[0]-1, 'cols': p[1]-x+1 };
r = mySuperBinarySearch(young, rect, what);
if r!=None:
return r;
rect = {'x': p[1]+1, 'y': y, 'rows': p[0]-y+1, 'cols': x+cols-p[1]-1 };
return mySuperBinarySearch(young, rect, what);
class youngMatrixSearcher:
def __init__(self):
self.compareOp = 0;
self.algebraicOp = 0;
self.call = 0;
self.binSearchCmp = 0;
def search( self, young, rect, what ):
x = rect['x'];
y = rect['y'];
rows = rect['rows'];
cols = rect['cols'];
if rows==0 or cols==0:
return None;
self.compareOp += 2;
k = (cols+0.0)/(rows+0.0);
self.algebraicOp +=2;
pos = lambda n: (int(y+n), int(x+n*k));
if (k > 1):
pos = lambda n: (int(y+n/k), int(x+n));
get = lambda p: young[p[0]][p[1]];
n = rows if k<1 else cols;
self.compareOp += 1;
if n==1 and get(pos(0)) != what:
return None;
self.compareOp +=2;
f = 0;
b = n;
m = 0;
m2 = -1;
self.algebraicOp += 4;
while m != m2:
m2 = m;
w = get(pos(m))
if( what < w ):
b = m;
elif( what > w ):
f = m;
else:
return pos(m);
m = (f+b)/2;
self.compareOp += 4;
self.algebraicOp += 9;
self.binSearchCmp += 2;
m = (f+b)/2;
self.algebraicOp += 2;
if( get(pos(m)) > what and m>0):
m = m-1;
self.algebraicOp +=2;
self.compareOp +=2;
p = pos(m);
w = get(p);
self.algebraicOp += 5;
if( w == what ):
return p;
self.compareOp += 1;
rect = {'x': x, 'y': p[0]+1, 'rows': y+rows-p[0]-1, 'cols': p[1]-x+1 };
self.algebraicOp += 6;
r = self.search(young, rect, what);
self.call += 1;
if r!=None:
return r;
self.compareOp += 1;
rect = {'x': p[1]+1, 'y': y, 'rows': p[0]-y+1, 'cols': x+cols-p[1]-1 };
self.algebraicOp += 6;
r = self.search(young, rect, what);
self.call += 1;
return r;
def test():
rows = 12;
cols = 12;
y = genRandomYoung( rows, cols );
print(y);
rect = {'x':0,'y':0,'rows':rows,'cols':cols}
searchFor = y[randrange(0,rows)][randrange(0,cols)];
print "searching for", searchFor;
s = youngMatrixSearcher();
p = s.search( y, rect, searchFor );
print "find at", p;
print "with ", s.algebraicOp, "algebraic operations; ";
print " ", s.compareOp, "comparisions; ";
print " ", s.binSearchCmp, "comparisions purely for searching;";
print " ", s.call, "calls.";
if( y[p[0]][p[1]] != searchFor ):
print 'oops';
else:
print ' - am i genius?'
def benchMark():
r=range(20,201);
ns = array([i for i in r]);
cs = array([0 for i in r]);
bcs = array([0 for i in r]);
for n in r:
avgc = 0;
avgbc = 0;
for i in range(10):
y = genRandomYoung(n,n);
w = y[randrange(0,n)][randrange(0,n)];
s = youngMatrixSearcher();
rect = { 'x':0, 'y':0, 'rows':n, 'cols':n };
s.search(y,rect,w);
avgc += s.compareOp;
avgbc += s.binSearchCmp;
avgc /= 10;
avgbc /= 10;
cs[n-ns[0]] = avgc;
bcs[n-ns[0]] = avgbc;
print ns;
print cs;
print bcs;
#test();
benchMark();
