Какова временная сложность циклов while?

Question

Я пытаюсь найти временную сложность циклов while, и я понятия не имею, с чего начать. Я понимаю, как найти класс сложности для циклов, но когда дело доходит до циклов, я полностью теряюсь. Любые советы/советы о том, с чего начать?

Вот пример задачи:

x = 0; 
A[n] = some array of length n; 
while (x != A[i]) { 
    i++; 
} 

Answer 1

Когда вам нужно сделать что-то n раз, вы должны сделать это n раз. Вы можете использовать цикл for, цикл while или что-то еще, что предлагает ваш язык программирования (или псевдо-код!). Грубая, большая заметка о примечании о количестве работы, которую вы должны делать, и не заботится о том, как вы это делаете (несколько менее грубо, она комментирует, как объем работы, которая должна быть выполнена, растет с растущим вкладом).

Продолжайте читать детали.

---

Я думаю, вы запутаны здесь. for и while - это конструкции языка программирования для выражения операций, которые необходимо повторить.

Анализ алгоритмов является агностиком языка реализации и не заботится о фактических конструкциях, которые вы используете при выражении алгоритма.

Рассмотрим следующее:

1. Input n 
2. Do OperationX n times 

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

1. Input n 
2. Input m 
3. Repeat m OperationX n times. 

Запись Big O будет сказать вам, что первая О (п), а второй является O (м * п) (при условии, что OperationX принимает постоянное время).

Вы можете написать код, используя конструкцию цикла по вашему выбору, это не имеет значения.

for(int i = 0; i < n; i++) { 
    operationX; 
} 

ли первая операция, и

i = j = 0; 
while(i < n) { 
    j = 0; 
    while(j < m) { 
     operationX; 
     j++; 
    } 
    i++; 
} 

второй. Большую нотацию O не волнует, было ли включено и выключено.

---

A[n] = some array of length n; 
for(x = 0;x != A[i];i++) { 

} 

Является for переписана вашего вопроса с той же сложностью (O(n)).