Метод расчета временной сложности алгоритма - PullRequest
Новая
       7

Метод расчета временной сложности алгоритма

0 голосов
/ 19 февраля 2019

Будучи несколько знакомым с интуитивным определением сложности алгоритмов, я немного растерялся, как на самом деле рассчитать его.

Для следующего кода, есть идеи, как я могу определить сложность? 

list = [...]
start = list[0]
end = null 
remove list[0] from list

while(list.length > 0) {
  for(i = 0; i < list.length; i++) {
    if(list[i] is immediately before start or immediately after end) {
       link list[i] to start or end (populate end if null)
       remove list[i] from list
    } 
  }
}

Это предполагает допустимый набор данных (непрерывно связанный список элементов, которые должны быть отсортированы).Также был упрощен в целях иллюстрации;

Итак, в лучшем случае это O (n), если список уже упорядочен, так как вам потребуется только проход, чтобы обработать их и вытащить их.

Что я не могу определить, так это наихудший сценарий, поскольку при каждой итерации "while" набор данных будет уменьшаться как минимум на 1 элемент (обычно на 2 или более), поскольку предполагается, что набор данных будет всегдадействительный.Так что это явно меньше, чем O (n ^ 2) (я думаю).Все идеи приветствуются.

Спасибо!

ОБНОВЛЕНИЕ После построения графика это выглядит как O (nlogk (n)), где k = n ^ (2 / (n + 1)) Это считается как O (nlog (n))?Мне неясно.

1 Ответ

0 голосов
/ 19 февраля 2019

Обозначение Big O предназначено для предоставления верхней границы для скорости роста функции, поэтому вы должны учитывать наихудший сценарий.

В худшем случае я бы предполагал в каждой итерации набор данныхбудет уменьшаться на 1 элемент, поэтому количество операций, которые вы будете выполнять, будет ограничено n + n-1 + n-2 ... + 2 + 1, что равно (n+1)*n / 2, что равно O (n ^ 2)

...