Какова сложность этого простого куска кода?

Question

Я вставляю этот текст из моей книги. Он говорит о сложности, если O (n ² ), а также дает объяснение этому, но я не вижу, как.

Вопрос: Каково время выполнения этого кода?

public String makeSentence(String[] words) {
    StringBuffer sentence = new StringBuffer();
    for (String w : words) sentence.append(w);
    return sentence.toString();
}

Ответ, который дала книга:

O (n ² ), где n - количество букв в предложении. И вот почему: каждый раз, когда вы добавив строку к предложению, вы создаете копию предложения и пробегаете все буквы в предложение, чтобы скопировать их Если вам нужно перебирать до n символов каждый раз в цикл, и вы делаете цикл не менее n раз, что дает вам время выполнения O (n ² ). Ой!

Может кто-нибудь объяснить этот ответ более четко?

Answer 1

Кажется, это вопрос заблуждения, потому что я прочитал эту книгу только сейчас. Эта часть текста в книге - опечатка! Вот контекст:

=============================================== ====================

Вопрос: Каково время выполнения этого кода?

1 public String makeSentence(String[] words) {
2 StringBuffer sentence = new StringBuffer();
3 for (String w : words) sentence.append(w);
4 return sentence.toString();
5 }

Ответ: O (n ² ), где n - количество букв в предложении. Вот почему: каждый раз, когда вы добавляете строку к предложению, вы создаете копию предложения и просматриваете все буквы в предложении, чтобы скопировать их. Если вам приходится повторять до n символов каждый раз в цикле и выполнять цикл не менее n раз, это даст вам время выполнения O (n ² ). Ой! С помощью StringBuffer (или StringBuilder) вы можете избежать этой проблемы.

1 public String makeSentence(String[] words) {
2 StringBuffer sentence = new StringBuffer();
3 for (String w : words) sentence.append(w);
4 return sentence.toString();
5 }

=============================================== ======================

Вы заметили, что автор все испортил? Упомянутое ею решение O (n ² ) (первое) было точно таким же, как и «оптимизированное» (последнее). Итак, мой вывод заключается в том, что автор пытался отобразить что-то еще, например, всегда копировать старое предложение в новый буфер при добавлении каждой следующей строки, как пример алгоритма O (n ² ). StringBuffer не должен быть таким глупым, так как автор также упомянул: «С помощью StringBuffer (или StringBuilder) вы можете избежать этой проблемы».

Answer 2

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

Тем не менее, я подозреваю, что человеку, задающему этот вопрос, не очень полезно просто сказать: «Ваша книга неверна!» - вместо этого давайте посмотрим, какие допущения делаются, и поясним, что автор пытался сказать.

Вы можете сделать следующие предположения:

1. Создание new StringBuffer - это O (1)
2. Получение следующей строки w в words равно O (1)
3. Возвращение sentence.toString - самое большее O (n).

Вопрос в том, каков порядок sentence.append(w), и это зависит от того, как это происходит внутри StringBuffer. Наивный способ сделать это, как Шлемиэль Художник .

Глупый путь

Предположим, вы используете строку с нулем в конце в стиле C для содержимого StringBuffer. Вы находите конец такой строки, читая каждый символ, один за другим, пока не найдете нулевой символ - затем, чтобы добавить новую строку S, вы можете начать копирование символов из S в строку StringBuffer (заканчивая с другим нулевым символом). Если вы пишете append таким образом, то это O ( a + b ), где a - количество символов, которое в данный момент находится в StringBuffer, b - количество символов в новом слове. Если вы перебираете массив слов, и каждый раз, когда вам нужно прочитать все символы, которые вы только что добавили, прежде чем добавлять новое слово, то сложность цикла составляет O (n ^ 2), где n - общее количество символов во всех словах (также количество символов в последнем предложении).

лучший способ

С другой стороны, предположим, что содержимое StringBuffer по-прежнему является массивом символов, но мы также храним целое число size, которое сообщает нам, какова длина строки (количество символов). Теперь нам больше не нужно читать каждый символ в StringBuffer, чтобы найти конец строки; мы можем просто посмотреть индекс size в массиве, который является O (1) вместо O ( a ). Тогда функция append теперь зависит только от количества добавляемых символов, O ( b ). В этом случае сложность цикла составляет O (n), где n - общее количество символов во всех словах.

... Мы еще не закончили!

Наконец, есть еще один аспект реализации, который еще не был рассмотрен, и это тот факт, который был затронут в ответе из учебника - распределение памяти. Каждый раз, когда вы хотите записать больше символов в ваш StringBuffer, вам не гарантируется, что в вашем массиве символов будет достаточно места для фактического размещения нового слова. Если места недостаточно, ваш компьютер должен сначала выделить несколько больше места в чистом разделе памяти, а затем скопируйте всю информацию в старом массиве StringBuffer, и затем она может продолжиться, как и раньше Копирование таких данных займет время O ( a ) (где a - количество символов для копирования).

В худшем случае вам нужно выделять больше памяти каждый раз, когда вы добавляете новое слово. Это в основном возвращает нас к исходной точке, где цикл имеет O (n ^ 2) сложность, и это то, что книга предлагает. Если вы предполагаете, что ничего сумасшедшего не происходит (слова не становятся длиннее с экспоненциальной скоростью !), То вы, вероятно, можете уменьшить количество выделений памяти до чего-то более похожего на O (log (n)) Распределенная память растет экспоненциально. Если это количество распределений памяти и общее выделение памяти O ( a ), то общая сложность, связанная только с управлением памятью в цикле, составляет O (n log (n)). Поскольку добавляемая работа равна O (n) и меньше, чем сложность управления памятью, общая сложность функции составляет O (n log (n)).

Опять же, документация по Java не помогает нам с точки зрения увеличения емкости StringBuffer, она просто говорит: «Если внутренний буфер переполняется, он автоматически увеличивается». В зависимости от того, как это происходит, вы можете получить либо O (n ^ 2), либо O (n log (n)).

В качестве упражнения, оставленного читателю: найдите простой способ изменить функцию, чтобы общая сложность составляла O (n), устраняя проблемы с перераспределением памяти.

Answer 3

Принятый ответ просто неверен.StringBuffer имеет амортизированное O (1) добавление, поэтому n добавлений будет O ( n ).

Если это не O (1) добавление,StringBuffer не будет иметь никаких оснований для существования, так как написание этого цикла с простой конкатенацией String также будет равно O ( n ^ 2)!

Answer 4

Я думаю, что этот текст в книге должен быть опечаткой, я думаю, что правильное содержание ниже, я исправляю это:

===================================================================

Вопрос: Сколько времени занимает этот код?

public String makeSentence(String[] words) {
    String sentence = new String("");
    for (String w : words) sentence+=W;
    return sentence;
}

Ответ: O (n ² ), где n - количество букв в предложении.И вот почему: каждый раз, когда вы добавляете строку к предложению, вы создаете копию предложения и просматриваете все буквы в предложении, чтобы скопировать их.Если вам приходится повторять до n символов каждый раз в цикле, и вы выполняете цикл как минимум n раз, это дает вам время выполнения O (n ² ).Ой!С помощью StringBuffer (или StringBuilder) вы можете избежать этой проблемы.

public String makeSentence(String[] words) {
    StringBuffer sentence = new StringBuffer();
    for (String w : words) sentence.append(w);
    return sentence.toString();
}

============================================================================

Прав ли я

Answer 5

Я пытался проверить это с помощью этой программы

public class Test {

    private static String[] create(int n) {
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            res[i] = "abcdefghijklmnopqrst";
        }
        return res;
    }
    private static String makeSentence(String[] words) {
        StringBuffer sentence = new StringBuffer();
        for (String w : words) sentence.append(w);
        return sentence.toString();
    }


    public static void main(String[] args) {
        String[] ar = create(Integer.parseInt(args[0]));
        long begin = System.currentTimeMillis();
        String res = makeSentence(ar);
        System.out.println(System.currentTimeMillis() - begin);
    }
}

И результат был, как и ожидалось, O (n):

Java тест 200000 - 128 мс

java-тест 500000 - 370 мс

java-тест 1000000 - 698 мс

версия 1.6.0.21

Answer 6

В этой книге есть опечатка.

---

1-й регистр :

public String makeSentence(String[] words) {
    String sentence = new String();
    for (String w : words) sentence += w;
    return sentence;
}

Сложность: O (n ^ 2) -> (n слов) x (скопировано n символов вкаждая итерация, для копирования текущего предложения в StringBuffer)

---

2-й случай :

public String makeSentence(String[] words) {
    StringBuffer sentence = new StringBuffer();
    for (String w : words) sentence.append(w);
    return sentence.toString();
}

Сложность: O (n) -> (n слов) x O (1) (амортизируемая сложность для конкатенации StringBuffer)

Answer 7

Это действительно зависит от реализации StringBuffer. Предположим, что .append() было постоянным временем, ясно, что у вас есть алгоритм O(n) во времени, где n = length of the words array. Если .append не является постоянным временем, вам необходимо умножить O (n) на временную сложность метода. Если в действительности текущая реализация StringBuffer копирует строки посимвольно, то приведенный выше алгоритм будет

Θ(n*m) или O(n*m), где n - это количество слов, а m - средняя длина слова, и ваша книга неверна. Я полагаю, вы ищете строгую границу.

Простой пример неправильного ответа книги: String[] words = ['alphabet'] По определению книги, n=8, поэтому алгоритм будет ограничен 64 шагами. Это тот случай? Явно не строго. Я вижу 1 назначение и 1 операцию копирования с n символами, так что вы получите около 9 шагов. Такое поведение предсказывается границами O(n*m), как я иллюстрировал выше.

Я немного покопался, и это явно не простая копия персонажа. Похоже, что память копируется массово, что возвращает нас к O(n), вашему первому предположению о решении.

/* StringBuffer is just a proxy */
public AbstractStringBuilder append(String str) 
{
        if (str == null) str = "null";
        int len = str.length();
        ensureCapacityInternal(count + len);
        str.getChars(0, len, value, count);
        count += len;
        return this;
}

/* java.lang.String */
void getChars(char dst[], int dstBegin) {
             System.arraycopy(value, offset, dst, dstBegin, count);
}

Ваша книга старая, ужасная или обе. У меня недостаточно решимости копаться в версиях JDK, чтобы найти менее оптимальную реализацию StringBuffer, но, возможно, такая существует.

Answer 8

Как пояснение в книге, для любого слова в массиве строк создается новый объект предложения, и этот объект предложения сначала копирует предыдущее предложение, а затем проходит до конца массива и затем добавляет новое слово отсюда и сложность n^2.

1. Первые 'n', чтобы скопировать предыдущее предложение в новый объект
2. Второй 'n', чтобы пройти этот массив и затем добавить его

Следовательно n*n будет n^2.

Answer 9

Вот мой расчет того, как они получили O (n ^ 2)

Мы проигнорируем время ЦП для объявления StringBuffer, так как оно не зависит от размера конечной строки.

При вычислении сложности O мы имеем дело с наихудшим случаем, это будет происходить, когда есть 1-буквенные строки.После этого примера я объясню:

Допустим, у нас есть 4 однобуквенные строки: «A», «B», «C», «D».

Читать в A: CPUвремя нахождения конца StringBuffer: 0 процессорное время для добавления 'A': 1

Чтение в B: процессорное время, чтобы найти конец StringBuffer: 1 процессорное время для добавления 'B': 1

Чтение в C: время ЦП, чтобы найти конец StringBuffer: 2 ЦП, время добавления 'C': 1

Чтение в D: ЦП, чтобы найти конец StringBuffer: 3 ЦПвремя добавления 'D': 1

Время ЦП для копирования StringBuffer в строку в конце: 4

Общее время ЦП = 1 + 2 + 3 + 4 + 4

Если мы обобщим это на n однобуквенных слов:

1 + 2 + 3 + ...... + n + n = 0.5n (n + 1) + n

Я сделал это, используя формулу для суммы арифметической последовательности.

O (0,5n ^ 2 + 1,5n) = O (n ^ 2).

Если мыиспользуя многобуквенные слова, нам придется реже находить конец StringBuffer, что приведет к сокращению времени процессора и к «лучшему» падежу.

Answer 10

Выглядит как O (n) для меня (с n - общее количество букв во всех словах). Вы просто перебираете каждый символ в words, чтобы добавить его в StringBuffer.

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

Самое большее, у вас будет O (m * n), где m - это количество увеличений длины буфера. И поскольку StringBuffer будет удваивать свой размер буфера каждый раз, когда он выделяет больший буфер, мы можем определить, что m приблизительно равен log2(n) (на самом деле log2(n) - log2(16), так как начальный размер буфера по умолчанию 16 вместо 1).

Таким образом, реальный ответ заключается в том, что примером книги является O (n log n), и что вы можете уменьшить его до O (n), предварительно выделив StringBuffer с достаточной емкостью, чтобы вместить все ваши буквы.

Обратите внимание, что в Java добавление к строке с использованием += демонстрирует неэффективное поведение, описанное в объяснении книги, так как оно должно выделять новую строку и копировать в нее все данные из обеих строк. Так что, если вы сделаете это, это O (n ^ 2):

String sentence = "";
for (String w : words) {
    sentence += w;
}

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