Является ли мой анализ времени и пространства правильным для этого алгоритма?
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)
В нижней строке будут найдены все файлы по заданному пути, проверяя, есть ли в имени файла
.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]
Аналогично, обход каталогов
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
Сложность пространства:
Пространство ввода
- суффикс -
O(1) - путь -
O(1) - path_elements + path_files + path_folders =>
O(e + f + g) => O(e)
Вспомогательное пространство
В рекурсии используется нечто, называемое "стек вызовов". Когда функция вызывает себя, эта функция попадает на вершину стека.
- В этом алгоритме рекурсивная функция исчерпывается, только если она прошла через все каталоги. Другими словами, когда он достиг
depth. Поэтому в стеке вызовов требуется O(depth) пространство.
Общая сложность пространства => Пространство ввода + Вспомогательное пространство => O(e + depth)