1

我想知道以下代码片段的时间复杂度，

FileReader fr = new FileReader("myfile.txt");
BufferedReader br = new BufferedReader(fr);

for (long i = 0; i < n-1; i++ ) {
   br.readLine();       
}
System.out.println("Line content:" + br.readLine());
br.close();
fr.close();

编辑：我想说，n = 一个常数，例如 100000

4

5 回答 5

4

复杂度是 O(n) 但这并不能告诉你太多，因为你不知道每个人需要多少时间readLine()。

当单个操作具有非常多变的运行时行为时，计算复杂性没有多大意义。

在这种情况下，循环非常便宜，不会对整个程序的运行时间贡献太多。另一方面，从磁盘加载对运行时间的贡献很大，但是如果没有关于每个文件的平均行数和行的平均长度的统计信息，就很难说。

于 2012-09-12T11:39:37.557 回答
2

这是一个非常简单的案例，但这里是如何找到时间复杂度的。相同的方法可以应用于更复杂的算法。

对于以下代码部分（并且无论 的复杂性如何readline()）

for (long i = 0; i < n-1; i++ ) {
   br.readLine();       
}

i = 0将被执行(n-1)次，i < n-1将被执行n次，i++将被执行n-1次，br.readline();将被执行n-1次。

这给了我们 n-1+n+n-1+n-1 = 4*n-3。这与 成正比n，因此复杂度为O(n)。

于 2012-09-12T11:46:02.323 回答
1

我不确定您所说的“时间复杂度”是什么意思，但它的性能似乎与它读取的文件大小呈线性关系（AKA O(n)）。

于 2012-09-12T11:37:47.013 回答
1

读取整个文件的时间复杂度应该是文件O(N)的N大小。

然而，鉴于所涉及的软件数量，证明这一点将很困难。main您已经在方法、Reader 堆栈（包括 Charset 解码器）和 JVM中获得了 Java 代码。然后你就有了操作系统中的代码。然后你必须考虑内核内存中的文件缓冲、文件系统组织、磁盘寻道时间等等。

（只考虑应用程序所花费的时间是没有意义的。我们可以有把握地预测，总时间所用的部分将被其他部分支配。）

而且，正如 Aaron 所说，复杂性度量不会成为实际文件读取时间的可靠预测指标。

于 2012-09-12T11:37:50.803 回答
1

readLine() 函数必须扫描输入的每个字符直到下一个换行符。这应该是 O(N)，其中 N 是前 n 行（您读取的）中的字节数。使用缓冲读取器不会降低算法复杂性，它只会减少读取给定字节数所需的实际 IO 调用次数（这是一件好事，因为 IO 调用很昂贵）。在这种情况下，唯一可以改变的方法是缓冲区的读取大小远大于您要读取的字节总数。

于 2012-09-12T11:40:52.663 回答