在以下场景中，空间复杂度和时间复杂度是如何工作的？

Question

请原谅，因为我对空间复杂性和时间复杂性都不是很熟悉。

我的问题是，

想象一下，在Java语言中有一段代码，它将读取一个.csv文件，然后将每一行打印到.txt中作为输出。

据我所知，时间复杂度在一定程度上取决于行数。空间复杂度是在运行时需要多少空间。(如果这是错误的，请向我简要介绍)

如上所述，如果我编写代码，将input.csv中的所有行一次性转换为某种数据结构，然后使用相同的数据结构将整个代码打印到output.txt中，会不会得到更差的空间复杂度，但更好的时间复杂度？此外，如果我逐行阅读，并在同一个循环中将它们打印到output.txt上，会不会带来更好的空间复杂度，但更差的时间复杂度？

如果问题不清楚，请一定要让我知道。提前谢谢。

Answer 1

空间复杂度和时间复杂度是算法的特性。

就空间复杂性而言，如果您读取一行，然后打印一行，那么您需要空间来存储该行作为算法的一部分。这取决于一行的最大长度。我假设输入文件可能只有一行。因此，这种方法的空间复杂度为O(n)，其中"n“是输入文件的大小，或者说是文件中最长的一行。

相比之下，将所有数据读取到内存中可能具有O(n)的空间复杂度。然而，数据结构可能很重要，这可能会使其成倍增加。

另一方面，一次读取CSV文件中的一个字符，然后写入该字符将使用恒定的空间--存储单个字符所需的任何空间。

至于时间复杂性，假设是读取每个字符，然后将其写出，因此时间似乎是O(n)。但是，如果数据以复杂的数据结构存储在内存中，那么这个大小也可能更大。

Answer 2

据我所知，时间复杂度在一定程度上取决于行数。空间复杂度是在运行时需要多少空间。

这基本上是正确的。你的时间将与输入呈线性关系，因为你将只处理一次所有的输入，因为你不会做任何魔术，比如主要的转换等等。也就是说，如果您低效地处理输入，您可能会在时间上引入大量开销，但这仍然是O(输入的大小)。

你的空间假设是正确的:你一次要使用多少空间？你是要使用其中的一小部分(如单个字符)、一部分(如一行)、多一点(如一些字节数的缓冲区)、整个(所有行，O(N))还是更大范围的东西，因为你必须存储额外的状态？

如果我编写代码，将input.csv中的所有行一次转换成某种数据结构，然后使用相同的数据结构将整个代码打印到output.txt中，会不会得到更差的空间复杂度，但更好的时间复杂度？

这可能会使您在空间上获得O(N)，其中N是输入的大小；您将整个内容存储在内存中。你的时间复杂度要复杂一点。从表面上看，你的时间是O(1)：你一次写下所有的东西。但由于编组数据、使用I/O等带来的开销和延迟，情况可能会更糟。在没有更多细节的情况下不容易回答。

如果我逐行阅读，并在同一个循环中将它们打印到output.txt上，会不会带来更好的空间复杂度，但更差的时间复杂度？

空格，是的:您的空间将是O(平均行大小)而不是O(所有输入的大小)。但请考虑最好和最坏的情况。最坏的情况是空格=O(输入的大小)时为O(行数)，因为只有一行！