Блог

Главная - Вопросы по программированию - Как оптимизировать это для цикла быстрее, чем O(N^3)?

Как оптимизировать это для цикла быстрее, чем O(N^3)?

#performance #for-loop #time-complexity

Вопрос:

Мой цикл for выводит все последовательные последовательности списка. Например, предположим, что список содержит [0, 1,2,3,4,5,6,7,8,9]. Он печатает,

  • 0
  • 0,1
  • 0,1,2
  • 0,1,2,3
  • ……..
  • 0,1,2,3,4,5,6,7,8,9
  • 1
  • 1,2
  • 1,2,3
  • 1,2,3,4,5,6,7,8,9
  • ……..
  • 8
  • 8,9
  • 9
 for i in range(10)
    for j in range(i, 10):
        subseq = []
            for k in range(i, j 1):
                subseq.append(k)
        print(subseq)

Текущая алгоритмическая сложность этого цикла for составляет O(N^3). Есть ли какой-либо способ ускорить этот алгоритм?

Комментарии:

1. Не следуйте своим циклам, но это похоже на проблему O(N^2)

Ответ №1:

Я не знаю Python (это Python, верно?), Но что-то подобное будет немного более быстрой версией O(N^3) (см. Комментарии ниже):

 for i in range(10):
    subseq = []
    for j in range(i, 10):
        subseq.append(j)
        print(subseq)

Да, это работает:

 [0]
[0, 1]
[0, 1, 2]
[0, 1, 2, 3]
[0, 1, 2, 3, 4]
[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 5, 6]
[0, 1, 2, 3, 4, 5, 6, 7]
[0, 1, 2, 3, 4, 5, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[1]
[1, 2] 
...
[7, 8]
[7, 8, 9]
[8]
[8, 9]
[9]

Комментарии:

1. Круто! Я не знаю, почему это никогда не приходило мне в голову. Мне нужно было что-то вычислить с помощью списка subseq, и я думаю, что мой мозг думал закончить составление списка subseq, а затем что-то с ним сделать после цикла for. Спасибо!

2. На самом деле это занимает время O(n^3). Хотя здесь всего два цикла, помните, что печать подмассива занимает время O(n), потому что в этом подмассиве может быть до n элементов.

3. @templatetypedef Сделает ли он код из вопроса O(n^4)?

4. Нет, это все равно будет O(n^3). Причина в том, что дополнительный цикл для создания массива текущих элементов выполняет (асимптотически) столько же работы, сколько и печать этих элементов. Тем не менее, это определенно медленнее, чем то, что у вас здесь, поскольку каждый раз он перестраивает подмножества с нуля, а не перерабатывает работу.

5. @templatetypedef спасибо! исправил свой ответ.

Ответ №2:

Это невозможно сделать менее чем за O(n 3) времени, потому что вы печатаете в общей сложности O(n 3) элементов. В частности, разделите массив на четверти и посмотрите на две средние четверти массива. Выберите любой элемент там — скажем, тот, который находится в позиции k. Это будет напечатано по крайней мере в n 2/4 различных подмассивах: выберите любой элемент в первом квартале, любой элемент в последнем квартале, и подмассив между этими элементами будет содержать элемент в позиции k.

Это означает, что любой из n / 2 элементов в середине двух кварталов печатается не менее n 2/4 раз, поэтому вы печатаете не менее n 3/8 общих значений. Нет способа сделать это лучше, чем за O(n 3) времени.

Метки: ,