hirax.net::Keywords::「計算量」のブログ

■交差点の位置を調べる「計算量」を京都の町で考える!?　

　京都の町では、多くの道が南北もしくは東西の方向に走っています。その結果、ほとんどの交差点は「直交する２つの道」により生まれ、そして、そんな交差点には「直交する２つの通りの名前を足された」名前が付けられるのです。

　だから、「南北という方向軸（＝道は東西に走る）」をX軸として、「東西という方向軸（＝道は南北に走る）」をY軸とすれば、すべての交差点はXY座標で示すことができることになります。だから、京都の交差点は「四条河原町(X=四条,Y=河原町)」とか「四条烏丸(X=四条,Y=烏丸)」とか「烏丸御池（X=御池,Y=烏丸）という具合に直行する２軸の座標値、すなわち通りの名前で表すことができ、その通りの名前を聞けば、どの場所に位置する交差点であるかが簡単にわかる、というわけです。XY座標で示される京都市街は、まさに「理系の散歩道」のために作られたような街、なのです。

京都の街で「非ユークリッド幾何学」を体感しよう!?

　もしもN本の東西の道と南北の道があるとしたら、交差点の総数はN^2ということになります。ということは、交差点の名称から場所を調べるための計算量は、O-記法で示すならO(N^2)もある、ということになります。これは、記憶力に問題がある私たちにはとても多すぎる量…です。

　ところが、いわゆる京都の街のような命名法を使っている場合には、つまり、「交差点の名称は、直交するふたつの通りの名称を結合することで作る」というルールにもとづくのであれば、東西・南北それぞれN本の通りの場所さえ覚えておけば、交差点名称から場所を調べるための計算量はたかだかO(2×N)≒O(N)にまで小さくなるのです。

　そんな計算量の削減・単純化ができるのは、「すべての道は直交する」という法則が、（「三条御池」というような特異点が生じることがない）京都中心街辺りではあるからです。

　交差点の信号機の下に掲げられた交差点の名称を長め、交差点の名称から場所を導き出すために必要な記憶量や計算量…そんなことを考え・楽しむことができるのが、「理系の散歩道」です。

　京都の街で、あなたの住む町で、「交差点の名称から場所を調べるための計算量」を考えてみることも楽しい」と思います。たとえば、あなたが知恵を絞れば、O(N^2)の計算が必要そうに思えるところをO(N log N)の計算量で済むようにすることができる…かもしれません。