0

ディレクトリを検索し、そのディレクトリとサブディレクトリ内のすべてのテキスト ファイルを検索するアルゴリズムがあります。親ディレクトリにサブディレクトリとサブサブディレクトリがいくつあるかわからないと仮定します。複雑さを計算するにはどうすればよいですか?

これは私が使用しているコードです

 public List<string> GetFilesInDirectory(string directoryPath)
    {            
        // Store results in the file results list.
        List<string> files = new List<string>();

        // Store a stack of our directories.
        Stack<string> stack = new Stack<string>();

        // Add initial directory.
        stack.Push(Server.MapPath(directoryPath));

        // Continue while there are directories to process
        while (stack.Count > 0)
        {                
            // Get top directory
            string dir = stack.Pop();

            try
            {             
                // Add all files at this directory to the result List.
                files.AddRange(Directory.GetFiles(dir, "*.txt"));                    

                // Add all directories at this directory.
                foreach (string dn in Directory.GetDirectories(dir))
                {
                    stack.Push(dn);
                }
            }
            catch(Exception ex)
            {

            }
        }

        return files;
    }

ありがとう

4

6 に答える 6

3

Big-O 記法は、引数のサイズが大きくなると、問題の複雑さがどのように大きくなるかを示しています。言い換えれば、要素のセットが増加したときに時間の複雑さがどのように増加するかです。1 個または 8972348932 個のファイル/ディレクトリは問題ではありません。ディレクトリとファイルが一度だけアクセスされると仮定すると、コードは O(N) 線形時間で動作します。O(123N) は引き続き O(N) と表記されます。これは何を意味するのでしょうか？Big O 表記は、実際の初期費用については何も言わないことを意味します。複雑さがどのように成長するかだけです。

O(N) 時間と O(N log N) 時間で実行される同じ問題の 2 つのアルゴリズムを比較します。O(N log N) アルゴリズムは、O(N) よりも小さい N の方が高速かもしれませんが、N が十分に大きい場合、O(N) は追いつきます。

于 2009-11-29T22:03:33.683 に答える
1

すべてのディレクトリのファイル数を合わせて O(N) だと思います。

これらのディレクトリをナビゲートすることは複雑な作業ではなく、単なる簿記です。

于 2009-11-29T21:46:53.500 に答える
1

アルゴリズムはスタック上のすべてのディレクトリをプッシュし、遭遇するすべてのディレクトリに対して機能するため、複雑さはディレクトリの 2 倍、または O(2n) の順序になります。ここで、n はディレクトリの数です。複雑さに関する限り、これは次のとおりです。 O(n) に相当します。

于 2009-11-29T21:50:17.037 に答える
0

時間の複雑さは で計算されます。nここで、nは処理中のアイテムの数になります。最悪の場合の実行時間を計算しようとしているため、正確な数値は必要ありません。

于 2009-11-29T21:46:39.067 に答える
0

最悪の場合、実行時間は、ディレクトリ ツリーの最大深度 (Windows では最大パス長によって制限されます) とサブディレクトリで許可されるファイル数の関数です。

于 2009-11-29T21:49:11.590 に答える
0

二重にネストされた for ループがあるため、O(N^2) と言えますが、各ループのサイズは同じではないため、少し変更する必要があります。

ディレクトリの数は、ファイルの数よりも少ない可能性があります。ファイルの数が N で、ディレクトリの数が M だとすると、O(N*M) になります。それが私の最善の推測です。

于 2009-11-29T22:53:14.070 に答える