2

面接で聞かれる質問は以下です。

あなたは非常に長い通りに置かれています。これはあなたが車を停めた通りです。この通りであなたの車を見つけなければなりません。

あなたの車を見つけるためのアルゴリズムとその複雑さは何ですか。彼らが探していた答えは O(nlogn) でした...しかし、なぜそれが o(nlogn) なのかを証明する必要があります... ヒント: この答えにたどり着くには多くの数学が必要です。

4

2 に答える 2

5

nこれが車までの距離だと思います。問題は、あなたが無限の通り/線の真ん中にいて、どちらの方向に行くべきかわからないことです.

これに対する解決策は、一方向に x ユニット、次に反対方向に 2x、次に 4x 前方、8x 後方など...そして必要な歩行はO(n*logn) O(n) です。

于 2012-08-29T22:42:26.893 に答える
0

これは、オンラインカウ パス問題の特殊なケースです。通常の測定基準は、車がどこにあるかを知っていた場合に移動する距離と比較した、最悪の場合の移動距離です (競争率)。これは 9n で、実際には O(n log n) であり、O(n log n) ではありません。ただし、O(log n) 回の方向転換を行います。

于 2012-08-29T23:06:41.823 に答える