java - 将所有子目录中所有文件中的所有数字相加 - 复杂性？

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 是该过程中发生的最大可能行数。您将每个文件中的每一行读取一次。因此，最坏的情况是您将读取 n 个文件中的 m 行。因此，它的复杂度为O(n*m)。您甚至可以将 m 视为平均行数。

您需要同时拥有 n 和 m 的原因是因为您有两个未知变量，即文件数量(如果其格式为一个文件和每个目录中的一个子目录，是否位于一个文件夹中并不重要，因为一条一条的去，需要全部访问一遍，而且每条只访问一次，还有行数。每一条都可以独立增长，所以是一个两个未知数的函数。因此，它的 O(n *m).

即使将所有行放入一个文件中，时间复杂度也是O(f(r))，其中f(r)=g(n*m) ，因此仍然是 O(n*m)，其中 r 是总行数 (r = n * m)。之所以功能不同，但顺序相同，是因为文件夹移动和文件读取启动的因素，这些因素应该是在算法开始之前定义的某个常量，不会影响函数的顺序。