如何提高算法时间复杂度？

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)。

没有神奇的方法可以降低问题的复杂性。有时您会因为初始算法效率不高而获得改进，有时则无法。在当前情况下，您可能无法（尽管这取决于特定的处理）。

通过对文件进行二次采样所做的事情并没有改善复杂性：减少问题的大小是一种欺骗，而且您也不再需要解决最初的问题。