Подходит ли мой анализ времени и пространства для этого алгоритма?

def find_files(suffix, path):
if suffix == '':
    return []

# Base condition
if len(os.listdir(path)) == 0:
    return []

path_elements = os.listdir(path)
path_files = [file for file in path_elements if ('.' + suffix) in file]
path_folders = [folder for folder in path_elements if '.' not in folder]

for folder in path_folders:
    path_files.extend(find_files(suffix=suffix, path=path + '/' + folder))

return path_files

# Tests
path_base = os.getcwd() + '/testdir'
print(find_files(suffix='c', path=path_base))

Объяснение: Рекурсия файла

Требование:

Цель состоит в том, чтобы написать код для поиска всех файлов в каталоге (и во всех каталогах ниже него), которые заканчиваются на ".c"

Резюме:

Чтобы реализовать это, я использовал функцию find_files, которая будет принимать suffix (расширение файла) и path (путь к каталогу, в котором нам нужно искать). В этой функции я рекурсивно ищу файл с заданным расширением в родительском каталоге и во всех его подкаталогах. Я сохраняю все эти файлы с заданным суффиксом в списке и возвращаю его.

Сложность времени и пространства:

Сложность времени:

os.listdir (путь) выведет список всех файлов и папок по заданному пути. Поскольку он должен перебирать каждый элемент, чтобы предоставить список, это требует линейной временной сложности. Пусть e будет длиной path_elements => O(len(path_elements)) => O(e)

path_elements = os.listdir(path)

2. Строка ниже обнаружит все файлы по заданному пути, проверив, есть ли .c в имени файла. Если s - это длина строки (имя файла / папки), то требуется O(s) времени, чтобы найти файл с заданным расширением. Следовательно, для f количества файлов требуется O(f*s) времени. Для практических целей, подобных этому, будет справедливо предположить, что имена файлов НЕ бесконечно длинные. Следовательно, мы можем принять s как константу => O(f * 1) => O(f).

path_files = [file for file in path_elements if ('.' + suffix) in file]

3. Точно так же переход по g каталогам займет линейное время => O(g)

path_folders = [folder for folder in path_elements if '.' not in folder]

Вышеупомянутые 3 шага потребуют => O(e + f + g) => O(e). Поскольку e (len(path_elements)) является доминирующим термином, поскольку представляет собой комбинацию path_files и path_folders

• Для рекурсии, если k - это количество каталогов (branches) на каждом уровне в depth, тогда рекурсия займет O(brancher^depth) => O(k^depth). Но для каждого рекурсивного вызова выполняется более трех шагов. Следовательно, общая временная сложность составляет O((k^depth) * e.

Сложность пространства:

1. Входное пространство

   • suffix - O(1)
   • путь - O(1)
   • path_elements + path_files + path_folders => O(e + f + g) => O(e)

2. Вспомогательное пространство

   Рекурсия использует так называемый «стек вызовов». Когда функция вызывает себя, эта функция идет поверх стека.

   • In this algorithm, the recursive function is exhausted only if it has traversed every directory. In other words, when it has reached the depth. Therefore O(depth) space is required in the call stack.

3. Общая сложность пространства => Входное пространство + Вспомогательное пространство => O(e + depth)