Алфавитный указатель Big-O Домашнее задание

for(int i=N; i>0; i=i/2) 
    irrelevant statement;

Прошу найти класс сложности, и я не уверен, должен ли я использовать нотацию Big-Omega или Big-O? Но я предполагаю, что это O (N/2), а затем O (N), если я отбрасываю константы.Алфавитный указатель Big-O Домашнее задание

for (int i=0; i<N; i++) 
    for (int j = i+1; j<N; j++) 
     irrelevant statement;

эту проблему, я считаю, что это O (N) * O (N + 1) -> O (N^2 + N), а затем O (N^2) после того, как я уронить N?

источник

2010-10-17 Steven

После перечитывания второго фрагмента кода я изменил свое предположение на O (N) * O (N-1) вместо O (N) * O (N + 1), потому что вложенный цикл получает итерацию на меньшее время, чем первый цикл, это правильно? Таким образом, это будет O (N (N-1)) == O (N^2-N) == O (N^2)? – Steven

удалил мой оригинальный комментарий, так как я неправильно прочитал первый цикл. Это действительно O (log2 (N)) –

Для первого, сколько еще операций выполняется, если вы удвоите N?

источник

2010-10-17 13:08:17

Если N удвоилось, у вас будет еще одна операция? – Steven

Стивен: Правильно, поэтому сложность не может быть O (N), потому что это будет означать, что число операций пропорционально N. –

Вы правы в отношении второго. Первый - это O (logN), а второй - O (N^2). Но есть один , но. То, что вы называете irrelevant statement, может быть очень актуальным. Если это утверждение было, например, вызовом функции, который, в свою очередь, работает в O (N), то сложности будут представлять собой O (N * logN) и O (N^3) соответственно. Итак, вы правы, если irrelevant statement - O (1).

источник

2010-10-17 13:14:59

Первый имеет класс сложности O (log2 (n)), так как при удвоении n он добавляет еще одну операцию.

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

источник

2010-10-17 13:15:33 Puppy

Алфавитный указатель Big-O Домашнее задание

ответ

Смежные вопросы