1

次のコードスニペットの時間計算量を知りたいのですが、

FileReader fr = new FileReader("myfile.txt");
BufferedReader br = new BufferedReader(fr);

for (long i = 0; i < n-1; i++ ) {
   br.readLine();       
}
System.out.println("Line content:" + br.readLine());
br.close();
fr.close();

編集：言いたいのですが、n =定数、たとえば100000

4

5 に答える 5

4

readLine()複雑さはO（n）ですが、それぞれに必要な時間がわからないため、あまりわかりません。

個々の操作の実行時の動作が非常に変動する場合、複雑さを計算してもあまり意味がありません。

この場合、ループは非常に安価であり、プログラム全体の実行時間にはあまり寄与しません。一方、ディスクからのロードは実行時間に大きく影響しますが、ファイルあたりの平均行数と行の平均長に関する統計情報がないと言うのは難しいです。

于 2012-09-12T11:39:37.557 に答える
2

これは非常に単純なケースですが、時間計算量を見つける方法は次のとおりです。同じ方法をより複雑なアルゴリズムに適用できます。

コードの次の部分について（およびの複雑さに関係なくreadline()）

for (long i = 0; i < n-1; i++ ) {
   br.readLine();       
}

i = 0（n-1）回実行i < n-1され、 n回i++実行され、 n-1回実行され、n-1br.readline();回実行されます。

これにより、n-1 + n + n-1 + n-1 = 4*n-3が得られます。これはに比例するnため、複雑さはO（n）です。

于 2012-09-12T11:46:02.323 に答える
1

「時間計算量」の意味はわかりませんが、パフォーマンスは読み取り元のファイルのサイズに比例しているように見えます（別名O（n））。

于 2012-09-12T11:37:47.013 に答える
1

ファイル全体を読み取る時間の複雑さはO(N)、Nファイルのサイズです。

ただし、関係するソフトウェアの量を考えると、これを証明することは困難です。mainメソッド、リーダースタック（文字セットデコーダーを含む）、およびJVMにJavaコードが含まれています。次に、OSにコードがあります。次に、カーネルメモリ、ファイルシステム構成、ディスクシーク時間などのファイルバッファリングを考慮する必要があります。

（アプリケーションにかかった時間だけを考えることは意味がありません。かかった合計時間の構成要素が他の構成要素によって支配されることを安全に予測できます。）

また、Aaronが言うように、複雑さの測定値は、実際のファイル読み取り時間の信頼できる予測子にはなりません。

于 2012-09-12T11:37:50.803 に答える
1

readLine（）関数は、次の改行までの入力のすべての文字をスキャンする必要があります。これはO（N）である必要があります。ここで、Nは最初のn行（読み取った）のバイト数です。バッファ付きリーダーを使用しても、アルゴリズムの複雑さは軽減されません。特定のバイト数を読み取るために必要な実際のIO呼び出しの数が減るだけです（IO呼び出しは高価であるため、良いことです）。この場合、状況を変える唯一の方法は、バッファの読み取りサイズが、読み取る予定の合計バイト数よりもはるかに大きい場合です。

于 2012-09-12T11:40:52.663 に答える