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

Question

private void listAll(int depth) 
{ 
    printName(depth); // Print the name of the object 
    if(isDirectory()) 
    for each file c in this directory (for each child) 
    c.listAll(depth + 1); 
} 

Я пытается использовать рекуррентное соотношение для индукции Время работы
Право время работы составляет O (N)
Мой анализ показывает, что это было бы быть O (N^2)

Вот моя индукция
1. T (0) = (строка один) O (1) + (линия 2) O (1) + (число детей, мы предполагаем, является N) N * (T (1)
2. T (0) = (линия 1) O (1) + (линия 2) O (1) + N * (O (1) + O (1) + N * (T (2))
3 Когда эта индукция продолжается, время работы будет каким-то O (N^2)

В чем проблема в моем анализе ???

Answer 1

Ваша ошибка заключается в допущении N детей. Если N - общее количество файлов, вы должны наблюдать за временем выполнения O (N).

Answer 2

Возможно, вы неправильно поняли, что означает N? Возможно, N - это количество всех файлов в корневом каталоге и всех его подкаталогах, что сделало бы эту проблему методом поиска по глубине, которая имеет сложность O (N), где N - количество узлов.

Если это действительно было N^2, то количество файлов в одном каталоге и в другом случае должно было бы иметь некоторую зависимость. Но это не так ... количество файлов в каждой папке не определено, если вы на самом деле не посещаете его. Это может быть 2, это может быть десять тысяч.

Answer 3

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

Таким образом, вы получаете O(N) (на самом деле, точно N * recursive_call_cost)