Как рассчитать сложность времени и пространства для следующей функции.

Question

Как рассчитать сложность времени и пространства следующей функции. Я пробовал, но меня путают из-за рекурсивных вызовов функций.

public void readDirectory(File file){ 
    if(file.isDirectory()){ 
     File[] folder = file.listFiles(); 
     for (File f : folder) { 
      readDirectory(f); 
     } 
    }else{ 
     if(file.getName().contains("(2)")) 
      System.out.println(file.getName()); 
    } 
} 

Answer 1

Это DFS. Сложность времени - O (n) (каждый раз вы просматриваете каждый файл) Пространство - это O (max {| каталог |}) для переменной folder.

Answer 2

Время = О (п)

• Для каждого уровня иерархии папок вы выполнить цикл for только для элементов на этом уровне. Если в файловой системе всего n элементов (файлов и папок), в каждой папке есть только часть этого номера, и все элементы в каждой папке суммируются до n. На каждом уровне рекурсии вы делаете линейное обход этого уровня и вызываете функцию для каждого ребенка. После выполнения для каждого уровня у вас все еще есть линейное время, потому что для каждого уровня, пройденного в линейном времени, только подразделение всех файлов и всех подразделений суммируется с общим количеством файлов.

Space = O (п)

• Аналогично у вас есть O(n) пространство-сложность, потому что выделить один File объект для каждого файла/папки в текущем пути. Фактически это равно максимальной глубине иерархии папок, потому что вы сохраняете объекты File на каждом уровне до окончания рекурсивного вызова следующего уровня, но освобождаете их только после этого. В худшем случае иерархия папок может быть O(n) глубокой - если в каждой подпапке имеется только одна вложенная папка и файлы отсутствуют. Это дает вам O(n) сложность пространства