algorithm - 如何提高我的算法时间复杂度？

Question

我们有“n”个文件，对于每个文件，“m”行，我们要进行一些操作，以处理所有文件和行，显然应用以下算法:

int n;    //n is the number of files 
int m;   //m is the number of the lines in the file i.
for(i=0;i<n;i++){
   for(j=0;j<m;j++){
            .....
   }
}

因此，我们的复杂度为 O(nxm)。

我的问题是:

是否有可能使其成为 O(nlog(n)) 或其他方法来提高算法的时间复杂度:

1- 保留所有文件和行。

2- 我们可以忽略其中的一些。

最好的问候

Answer 1

如果你想玩渐近复杂性，那就要严谨。

初始复杂度为 Θ(F L)(最有可能，但您未指定处理)其中 F 表示文件数，L 每个文件的平均行数。 (不过，由于行的长度可能会有所不同，所以用平均字符数来说话会更安全。)

如果您处理与 F 中的位一样多的文件(就像您所做的那样)，复杂性确实会降低到 Θ(log(F) L)。但是，如果您处理所有其他文件，甚至处理其中的十分之一，复杂性仍然是 Θ(F L)。

---

没有降低问题复杂性的 Elixir 。有时您可以获得改进，因为初始算法效率不高，有时则不能。在手头的情况下，您可能不能(尽管这取决于特定的处理)。

你通过对文件进行子采样所做的并不是复杂性的改进:它是一种减少问题大小的作弊，你不再解决最初的问题。