Что является более формальной сложностью O (n / 2)? - PullRequest
Новая
       11

Что является более формальной сложностью O (n / 2)?

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

Мне нужно знать, как анализировать алгоритмы с точки зрения дискретного математического класса.Это не домашняя работа, пример от здесь в 1: 54 .Значит, мне нужно знать константы, а не только общие биг-0.Это метод или алгоритм, с которым я запутался.Не было бы 3n/2 + 1.

Я думаю, что для первого метода цикл for выполняется n(1/2) + 1 раз, а внутри цикла оператор выполняется n раз или, может быть, O(1/2) раз внутри какЧто ж.Затем добавьте эти два.

Для последующего метода цикл выполняется n + 1 раз и n внутри.Поэтому я верю, что это будет (n + 1) + n.Итак, 2n + 1.Это процесс, которому я следую для первого метода, но я не настолько уверен в себе. 

for(i = 0; i < n; i = i+2) { // n(1/2) + 1
    do something; //n
}

for(i = 0; i < n; i = i++) { // n + 1
    do something; //n
}
...