В худшем случае сложность времени

Question

У меня есть алгоритм, который ищет в каталоге и ищет все текстовые файлы в этом каталоге и в любом подкаталоге. Предполагая, что я не знаю, сколько подкаталогов и вложенных подкаталогов находится в родительском каталоге. как рассчитать сложность?

это код, который я использую

 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;
    }

спасибо

Answer 1

Нотация Big-O говорит о том, как растет сложность проблемы при увеличении размера аргумента. Другими словами, как возрастает сложность времени, когда увеличивается набор элементов. 1 или 8972348932 файлов / каталогов не имеет значения. Ваш код работает за O (N) линейное время, при условии, что каталоги и файлы посещаются только один раз. O (123N) все еще записывается как O (N). Что это значит? Это означает, что нотация Big O ничего не говорит о фактической первоначальной стоимости. Только с ростом сложности.

Сравните два алгоритма для одной и той же задачи, которая выполняется за O (N) и O (N log N) времени. Алгоритм O (N log N) может быть быстрее для меньшего N, чем алгоритм O (N), но при достаточно большом N O (N) наверстает упущенное.

Answer 2

Ваш алгоритм выталкивает все каталоги в вашем стеке и работает для каждого каталога, с которым он сталкивается, поэтому сложность имеет порядок порядка каталогов, умноженных на 2, или O (2n), где n - это количество каталогов, насколько сложность касается это эквивалентно O (n).

Answer 3

Я бы сказал, что это O (N) по количеству файлов вместе во всех каталогах.

Навигация по этим каталогам не сложная задача, это просто бухгалтерия.

Answer 4

Я бы сказал, что это O (N ^ 2), потому что у вас есть цикл с двойным вложением, но размер каждого цикла не одинаков, поэтому мы должны немного его изменить.

Количество каталогов, вероятно, меньше, чем количество файлов. Итак, допустим, что количество файлов равно N, а количество каталогов равно M, тогда вы получите O (N * M). Это мое лучшее предположение.

Answer 5

в худшем случае время выполнения зависит от максимальной глубины дерева каталогов (в окнах оно ограничено максимальной длиной пути) и количества файлов, разрешенных в подкаталоге

Answer 6

Сложность времени рассчитывается в единицах n, где n будет количеством обрабатываемых элементов. Вам не нужны точные числа, и более того, вы не можете использовать точные числа для сложности больших чисел, так как вы пытаетесь вычислить худший случай время выполнения.