В чем сложность этого алгоритма? (Джава) - PullRequest
Новая
       9

В чем сложность этого алгоритма? (Джава)

0 голосов
/ 06 января 2019

Цикл while равен O(logn). Будет ли работать внутренний цикл O(n), так как он объединит максимум n символов (в результате всего O(logn + n))? Будет ли использование StringBuilder сделать его O(1)? 

List<String> l = new ArrayList<>();
// some code to add N items to l
//.
//.
//.
while (l.size() > 1) {
    int lo = 0, hi = l.size() - 1;
    List<String> temp = new ArrayList<>();
    while (lo < hi) {
        temp.add("(" + l.get(lo) + "," + l.get(hi) + ")");
        lo++;
        hi--;
    }
    l = temp;
}

1 Ответ

0 голосов
/ 10 января 2019

Я придумал несколько решений, лучшее из которых - вывести строку - модификацию вашего исходного поста.

Это решение будет соответствовать алгоритмическому времени использования StringBuilder (l.size * 2 -1). * 2 - 1 - для запятых.

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

Вся сложность составляет 1/2 * N + (1/2 * (N - 1) + (1/4 * (N - 2)) + (1/8 * (N -3)) ... ) * +1010 *

Моя математика / анализ могут быть неверными, однако нижняя граница задана тем, что для конкатенации строк всех элементов массива требуется как минимум N операций => O (N) Верхняя граница, при условии, что моя математика верна выше, также равна O (N). Поскольку все, что меньше половины значения, не может быть добавлено к значению, чтобы итоговое значение превысило исходное значение.

Если моя математика неверна, наихудшим случаем является N log N.

Абсолютная верхняя граница равна N в квадрате (если вы игнорируете факт, N уменьшается при каждой итерации). 

List<String> l = new ArrayList<>();
// some code to add N items to l
//.
//.
//.
while (l.size() > 1) {
    int lo = 0, hi = l.size() - 1;
    List<String> temp = new ArrayList<>(l.size/2 + 1);
    while (lo < hi) {
        temp.add("(" + l.get(lo) + "," + l.get(hi) + ")");
        lo++;
        hi--;
    }
    l = temp;
}

На практике ограничивающим фактором алгоритма становится выделение и перераспределение памяти в 1/2 N списков массивов для всех значений N, кроме малых и средних,

...