Суммируйте все числа во всех файлах, представленных во всех подкаталогах - сложность?

Question

Имея корневой каталог, читайте все файлы построчно внутри rootDirectory или подкаталогов и суммируйте все числа из каждого файла.Каждый файл будет иметь номер в каждой строке.Так что мне просто нужно прочитать все файлы, сложить все числа и вернуть их.Я придумал приведенный ниже код, и он выполняет свою работу (если есть какой-то лучший или эффективный способ, дайте мне знать) ..

Я пытаюсь понять, в чем сложность программы, представленной ниже.Если структура очень глубокая и у нас много файлов во многих подкаталогах, то какова будет сложность приведенной ниже программы.Как описать сложность в этом случае, если об этом спросят в интервью?

  private static int count = 0;

  public static void main(String[] args) {
    System.out.println(sumNumbersInFile("/home/david"));
  }

  private static int sumNumbersInFile(String rootDirectory) {
    if (rootDirectory == null || rootDirectory.isEmpty()) {
      return 0;
    }

    File file = new File(rootDirectory);
    for (File fileEntry : file.listFiles()) {
      if (fileEntry.isDirectory()) {
        count += sumNumbersInFile(fileEntry.getName());
      } else {
        try (BufferedReader br = new BufferedReader(new FileReader(fileEntry))) {
          String line;
          while ((line = br.readLine()) != null) {
            count += Integer.parseInt(line);
          }
        } catch (NumberFormatException | IOException e) {
          e.printStackTrace();
        }
      }
    }
    return count;
  }

Answer 1

Допустим, у вас есть n файлы.Итак, вы посещаете каждый файл один раз.Так что эта часть O(n).Допустим, m - максимально возможное количество строк, которое происходит в этом процессе.Вы читаете каждую строку в каждом файле один раз.Таким образом, в худшем случае вы будете читать m строк в n файлах.Итак, это делает его O(n*m).Вы можете посмотреть на m даже как на среднее число строк.

Причина, по которой вам нужны n и m, заключается в том, что у вас есть две неизвестные переменные, число файлов (не имеет значения,в одной папке, отформатированной как один файл и один подкаталог в каждом каталоге, так как вы идете по одной, вам нужно посетить все это, и вы посещаете его только один раз в каждой, и количество строк. Каждая из них может расти независимо,так что это функция двух неизвестных. Следовательно, это O(n*m).

Даже если вы поместите все строки в один файл, это будет O(f(r)), где f(r)=g(n*m), так что все равно будет O(n*m), где r - общее количество строк (r = n * m). Причина, по которой он имеет другую функцию, но все еще в том же порядке, из-за коэффициента перемещения по папкам и начала чтения файла, который должен быть некоторой константой, определенной до началаалгоритм, который не влияет на порядок функции.

Answer 2

Вы все еще делаете только один шаг вычисления на строку.Алгоритм: O(n), где n - количество строк во всех файлах.