Как анализировать сложность алгоритма?

Question

У меня есть несколько примеров, в которые я сейчас застрял. По достоинству оцените ваши советы и как это сделать. Каковы наилучшие и худшие случаи для этих примеров?

• Пример 1

• Пример 2

• пример 3

Answer 1

Я не собираюсь давать вам ответы. Но вот пример того, как я буду обращаться к нему с комментариями.

for(int i = 0; i < N; i++) //This line is executed N times 

    for(int j = i; j < N; j++) // This line is executed (N - i) times, for every N 

     doSomeWorkOn(i, j); //This can add complexity as well, but let's assume we're trying to figure out how many times this is called. 

Обратите внимание, что каждый раз, когда мы запускаем первый цикл, количество работы, которое мы делаем во втором цикле, уменьшается. Это усложняет ситуацию. Если наш внутренний цикл чтения

for(int j = 0; ......) 

Тогда ответ прост, это просто N * N. N раз, что нам нужно сделать N объем работы. В этом случае у нас есть

N + (N-1) + (N-2) .... (NN) Если вы затем математическая серия Google, вы обнаружите, что это упрощает (N (N + 1)))/2.

EDIT:

Примечание это, вероятно, будет легче найти серию, если вы делаете это в обратном направлении от того, что я сделал, это означает

0+1+2+...(N) = N + (N-1) + (N-2) ... (0) = (N(N+1))/2 

1-ый подход является наиболее распространенным. У меня есть привычка делать это в обратном порядке, потому что у меня есть таблица серий, запомненная, и, видя ее по отношению к N, более значима для меня, но, с точки зрения новичка, вам, скорее всего, легче начать в нижнем конце, так как это то, как большинство страниц помощи/текстовых книг/профессоров будут представлять его. Это, однако, идентично. Какой бы путь вам ни был проще.

Answer 2

Похоже, домашнее задание для класса алгоритмов для меня, но для анализа итеративных алгоритмов вам необходимо использовать правила суммирования. Введение в дизайн и анализ алгоритмов от Anany Levitin - хорошая книга.

И идти вместе с тем, что сказал ChrisCM -

Взятые прямо из книги:

Полезные правила: