В чем сложность этого простого фрагмента кода?

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

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

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

Ответ в книге было написано:

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

Кто-нибудь, пожалуйста, объясните этот ответ более четко?

31
задан templatetypedef 5 January 2013 в 06:44
поделиться