How do you calculate number of accesses for a sequential search if record is present, not present, or sometimes present?
What about for binary search?
1 に答える
0
まず、検索するもののリストを想像します (または、私のように想像力に挑戦している場合は紙に描きます) - シンプルに保ち、整数の順序付けられたリストにします。次に、整数を考えます。リストの最初の要素に鉛筆 (または思考) を置き、片手で親指を曲げて、自分自身に 1 を数えます。最初の要素が必要なものである場合は、別の紙に 1 を書き、別の数字を選んでやり直します。最初の数字が探している数字でない場合は、鉛筆を 1 つの数字に沿って動かし、2 を数えて、手の人差し指を曲げます。探している番号またはない番号が見つかるまで続けます。
退屈するか、質問に対する答えが何であるかを理解するまで、このプロセスを繰り返します。これを皮肉なコメントと考えないでください。この種のことを理解する方法を教えることを目的としています。
二分探索については、リストの真ん中にある要素を見てください。1 を数えます。それはあなたが探している要素ですか? そうでない場合は、探している要素よりも大きいですか? そうである場合は、リストの左側の中央を見てください。そうでない場合は、リストの右側の中央の要素を見てください。探している要素が見つかるまで、数えて繰り返します。
鉛筆と紙を使っていくつかの例に取り組むことは、コンピューターが何をしているかを理解するための優れた方法です。そして、経験上、非常にトリッキーなコードをこの方法でデバッグする日が来るので、卒業してプロのプログラミングに進むことができれば、非常に役に立ちます。
于 2010-03-16T09:17:43.927 に答える