Сложность времени нахождения всех возможных подмассивов массива - PullRequest
Новая
       77

Сложность времени нахождения всех возможных подмассивов массива

0 голосов
/ 24 февраля 2020

Согласно реализации поиска всех возможных подмассивов из данного массива следующим образом: 

public class AllPossibleSubArray {

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3 };
        List<List<Integer>> result = new ArrayList<>();

        for (int len = 0; len <= arr.length; len++) {
            if (len == 0) {
                result.add(new ArrayList<>());
            } else {
                for (int i = 0; i < arr.length - len + 1; i++) {
                    List<Integer> temp = new ArrayList<>();
                    for (int j = i; j < i + len; j++) {
                        temp.add(arr[j]);
                    }
                    result.add(temp);
                }
            }
        }

        result.forEach(System.out::println);
    }

Согласно моему пониманию, сложность по времени будет O (N ^ 3), поскольку есть три FOR l oop.

Но эта проблема не что иное, как набор мощности, то есть поиск всех возможных поднаборов из данного набора. На различных форумах в сети сложность времени равна 2 ^ N (биномиальное расширение), которое не совпадает с O (N ^ 3).

Мне не хватает фундаментальных?

1 Ответ

2 голосов
/ 24 февраля 2020

Но эта проблема не что иное, как набор мощности, то есть поиск всех возможных поднаборов из данного набора.

Это не правильно.

Код, который вы ' ve отправил только найденные смежные подмассивы, что означает список всех элементов от одного индекса к другому.

Набор мощности, напротив, также будет включать в себя непрерывные подпоследовательности Это означает, что они включают в себя два элемента без включения всех элементов между ними.

Следует также отметить, что существует только O ( n 2 ), и если вы найдете другой способ их представления, вы можете найти их в O ( n 2 ), а не в O ( n 3 ) как код, который вы опубликовали. (В частности, вам необходимо представление, которое позволит вам повторно использовать общие части списков, а не копировать все необходимые элементы каждый раз.) В отличие от этого, если вы придерживаетесь представления в своем коде, где каждый список имеет отдельную копию нахождение всех подмножеств на самом деле потребует O ( n · 2 n ) времени, а не просто O (2 n ) время.

...