В чем сложность этого кода?И какую нотацию я должен использовать? - PullRequest
Новая
       13

В чем сложность этого кода?И какую нотацию я должен использовать?

0 голосов
/ 07 марта 2012

Когда я определяю сложность Java-кода, подобного этому, нужно ли мне выражать это в тэте или большой букве O? 

List<Person> sortedPersons = new ArrayList<Person>();
List<Person> people = new ArrayList<Person>();

    for (int i = 0; i < people.size(); i++) {
        Person toadd = people.get(i);

        int index = 0;
        while(index < sortedPersons.size() && sortedPersons.get(index).compareTo(toadd) < 0)
            index++;

        sortedPersons.add(index, toadd);

    }

Я знаю, что цикл for равен O (n)(или это \ Theta (n)?) Операция get выполняется за постоянное время, поэтому O (1).Но как насчет цикла while?sortedPersons.size (): O (1) sortedPersons.get (): O (1) Является ли операция сравнения линейной?И я думаю, что операция добавления также выполняется в постоянное время.Какова общая сложность кода?

1 Ответ

1 голос
/ 07 марта 2012

код O (n²) Если вы учитываете числа и сортируете их от малого к большому.

  • Если ваш ввод сортируется в обратном порядке (от большого к маленькому), код будет Θ(n).
  • Если ваш ввод уже отсортирован, этот код будет Θ (n²)

Код является лишь вариантом Вставка сортировки ,он просто использует список вместо массива.

Рассмотрите этот пример для сложности:

Числа 1 2 3 4 5, и вы хотите отсортировать от малого до большого.

  1. После первого изменения ваш список будет состоять из 1. (это происходит в o (1)), и вы не будете посещать внутренний цикл.
  2. Во втором обновлении у вас есть список {1}, так как вы вставляете 2, вы посещаете цикл while один раз, после того, как вы его вставите.
  3. Третье изменение в списке: {1 2}, вы дважды посещаете цикл while и вставляете 3 после него..
  4. ...

В итоге у вас будет что-то вроде: 0 1 2 3 4 раза побывало в гостиницеer loop.

Теперь вы можете написать 1 2 3 4 5 как (5 (5 + 1)) / 2).

Теперь вы можете написать O (n (n + 1) /2 + n) как O (n²).

...