Вычисление большого "O" для следующего примера

#algorithm #big-o

#алгоритм #большой-o

Вопрос:

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

 int number;
for(int i = 0; i < A; i  )
    for(int j = 0; j < B; j  )
        if(i == j) // some condition...
            do{
                number = rand(); 
            }while(number > 100);

Я хотел бы знать большую букву «О» для этого примера. Внешние циклы — это O (A * B), но я не уверен, что думать о do-while цикле, и это большое «O». В худшем случае это может быть бесконечный цикл, а в лучшем случае O(1) и игнорируется.

Редактировать: обновлено условие внутри if инструкции (заменен вызов функции простым сравнением).

1. Ответ полностью зависит от реализации someCondition() , а также от того, какой диапазон значений rand() может возвращать. Вы должны включить эту информацию в свой вопрос.

2. @TimBiegeleisen Если if оператор не будет вызовом функции, но что-то вроде, i == j тогда я предполагаю, что if оператор будет O (1)? rand() может возвращать любое int число. Не могли бы вы, пожалуйста, объяснить, насколько важен его диапазон в этом случае внутри do-while цикла?

Ответ №1:

Хотя rand() это случайная функция и она имеет заданный диапазон выходных данных, мы можем сказать, что do while оператор равен O(1). Итак, это зависит от someCondition() функции.

Общая сложность равна O(A * B) * O (некоторое условие).

1. Если if оператор будет не вызовом функции, а чем-то вроде i == j , то я предполагаю, что if оператор будет O (1)?

2. Кроме того, я действительно не понимаю, почему do-while сложность в этом случае равна O (1)?

3. Если if оператор не является вызовом функции, то сложность будет равна O(A*B)

4. Предположим, что выходные данные rand() функции имеют диапазон от 0 до MAX_NUM. Тогда вероятность того, что число будет меньше 100, равна 100 /MAX_NUM. Итак, do while оператор прерывается в MAX_NUM/100 раз в среднем. Итак, мы можем сказать, что сложность do while равна O(MAX_NUM/100)= O(1).

5. @Tracer: дело в том, что это не имеет значения, это можно рассматривать как константу. Это не способствует асимптотическому росту.