- 254 名前：デフォルトの名無しさん mailto:sage [2009/09/24(木) 01:18:09 ]
- >>253
それでいいのならソート自体が目的ではないのでO(n)のメモリが必要なデータ構造を用意する必要はない。
ファイルをスキャンしながら検索対象以下の数値の個数をカウントして、
最後まで読み終わった時点で検索対象が現れていたら、
現れた行番号が「乱数ファイル上の行番号」であり、
検索対象以下の数値の個数が「昇順でソートした際の順序番号」になるので、
行番号と個数を覚えておくだけのO(1)のメモリで済むしファイルを読んだ後の探索もいらない。
でもこれって結局ファイル上ではあるもののO(n)の探索には変わりないんだよね。
ファイルを一通り読んでいいのに探索はO(n)では駄目とかの>>245の要求が矛盾しているというか。
