Как улучшить мой алгоритм временной сложности?

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

---

Не существует волшебного рецепта, чтобы уменьшить сложность проблемы. Иногда вы можете получить улучшения, потому что первоначальный алгоритм неэффективен, иногда вы не можете. В данном случае вы, вероятно, не можете (хотя это зависит от конкретной обработки).

То, что вы делаете путем подвыборки файлов, не является улучшением сложности: это обман для уменьшения размера проблемыи вы больше не решаете исходную проблему.

Answer 2

1. Вы можете достичь m log (n), пропустив n / log n файлов

или

Вы можете достичь n log (m), пропустив m / log m строк на файл.