图灵机上的荷兰国旗上有一条带n.log(n)复杂度的色带?

最后发布: 2015-11-07 14:21:03


问题

荷兰的国家问题是这个问题:我有一个字符序列x ^ k(k> = 3)我的目标是将这句话转换成荷兰语标记,也就是说:

xxx给RWB

xxxx给RWBB

xxxxx给RWWBB

xxxxxx给RRWWBB

...

其中R <= W <= B <= R + 1

我想设计一个带状的图灵机,其复杂度为n.log(n)。 事实是,标准算法正在使用交换,而我不能使用它,在这种图灵机中这是不可用的(效率不够)。

你知道怎么做吗? :)

algorithm complexity-theory turing-machines dutch-national-flag-problem