书中判断两个雪花是否“本质相同”的代码长得像这样:
bool equal ( int *a, int *b ){
for ( int i = 0; i < 6; ++i )
for ( int j = 0; j < 6; ++j ){
balabala
for ( int k = 0; k < 6; ++k ) balabala
balabala
for ( int k = 0; k < 6; ++k ) balabala
balabala
}
}
可以看出其判断一对雪花的时间复杂度上界最少为 6 * 6 * (6+6)=432 次比较。
而如果我们以O(n)的时间复杂度上界求出每个雪花的最小表示,那么我们就能通过以下代码以最少 (6+6)=12 次比较判断一对雪花是否“本质相同”:
for ( int j = 0; j < 6; ++j ){
if ( a [j] != minex [i][0][j] ) break;
if ( j == 5 ) return false;
}
for ( int j = 0; j < 6; ++j ){
if ( a [j] != minex [i][1][j] ) break;
if ( j == 5 ) return false;
}
其中a、minex[][0]为正序排列雪花六角的最小表示,minex[][1]为倒序排列雪花六角的最小表示。