2 
private void listAll( int depth )
{
    printName( depth ); // Print the name of the object
    if( isDirectory( ) )
    for each file c in this directory (for each child)
    c.listAll( depth + 1 );
}

漸化式を使用して実行時間を誘導しようとしています
正しい実行時間はO（N）です
私の分析では、O（N ^ 2）になることが示されています

これが私の誘導
1です。T（0）=（1行目）O（1）+（2行目）O（1）+（私たちが想定する子の数はNです）N *（T（1）
2. T（0 ）=（1行目）O（1）+（2行目）O（1）+ N *（O（1）+ O（1）+ N *（T（2））
3この誘導が続くと、時間はある種のO（N ^ 2）になります

私の分析の問題は何ですか？

4

3 に答える 3

4

あなたの誤りはN人の子供を仮定することです。Nがファイルの総数である場合、O（N）ランタイムを監視する必要があります。

于 2013-03-14T20:01:17.253 に答える
0

N の意味を誤解しているのではないでしょうか? おそらく、N はルート ディレクトリとそのすべてのサブディレクトリ内のすべてのファイルの数であり、N がノードの数である場合、O(N) の複雑さを持つ深さ優先検索の問題が発生します。

実際に N^2 である場合、一方のディレクトリと他方のディレクトリのファイル数には何らかの依存関係が必要です。しかし、そうではありません...実際にアクセスしない限り、各フォルダー内のファイルの数は不定です。2 の場合もあれば、1 万の場合もあります。

于 2013-03-14T20:03:15.853 に答える
0

1 つのステップが 1 回の呼び出しを意味し、listAll()がNディレクトリ構造内の要素の総数である場合、1 回の呼び出しが 1 つlistAll()の要素に対応している必要があります。そうしないと、少なくとも 1 つの要素が複数回出力されます。

したがって、O(N)(実際には、正確に N * recursive_call_cost)が得られます。

于 2013-03-14T20:03:58.263 に答える