O（logN）排序
排列n个1至128的整数……n<=128
搞128个7 to 128 译码器，128个7位输入端，128个8位寄存器
128个8位寄存器有128×8个位置，记作数组b[128][8]，初始值都是0
128个输入端同时接受输入，记作数组a[128][7]
每个输入端分配一个译码器，第 i 个译码器的第 j 位输出记作数组c[i][j]
0<=j<=6: b[i][j] = Or(a[0][j]&c[0][i], a[1][j]&c[1][i], ..., a[n][j]&c[n][i])
b[i][7] = Or(c[0][i], c[1][i], ..., c[n][i])
然后128个8位寄存器的前7位依次是从小到大排列的输入数列，第8位表示数据是否有效
以上机器只有一层译码和两层门的延迟
译码可以用(log128)=7层门来解决，这里是O（logN）的由来
评论0