Продолжительность программ

у меня есть вопрос к времени работы следующие программы: Проблема 1:Продолжительность программ

a = 0 
for i = 1 to n: 
    if i is odd: 
     for j = 1 to i: 
      a = a + j

Задача 2:

k = n 
while k >= 1: 
    k = k/2

Что время работы этих двух задач с использованием большого О и большая Тета?

Для первого вопроса первая строка - O (1), внешняя петля - O (n). Я немного смущен внутренним циклом for, поскольку он связан с j. Я думаю, что когда n - большое нечетное число, тогда это будет O (n^2) из-за вложенного цикла.

Для второго вопроса, я думаю, что для k будет меньше n/2 раз, чтобы быть меньше 1., но не уверен, что это O (n) или большая тета n.

источник

2016-01-19 Patrick123

Как вы думаете, и почему? Где у вас проблемы с анализом? * Что вы сделали до сих пор? * –

@ Джон Коулман Не совсем. Я просто хочу убедиться, что мой ответ правильный или нет. Для первой проблемы внешний цикл равен O (n), а внутренний цикл связан с j, но не n. Я думал, что это будет O (n^2), но не уверен. Для второй проблемы мой ответ - большая тета n, так как для повторения цикла потребуется n/2 раза. – Patrick123

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

Анализ первой проблемы, по сути, является правильным. Ключевым моментом ингредиентом является классическая идентичность

1 + 3 + 5 + ... + (2k-1) = k^2

в этом случае 2k-1 = n (или n-1), поэтому сложность O((n/2)^2) = O(n^2)

Для второй задачи - это классическая проблема типа разделяй и властвуй. Ключевой вопрос: сколько раз вам нужно разделить n, чтобы добраться до 1? Это эквивалентно заданию того, сколько раз вам нужно умножить 1 на 2, чтобы добраться до n? Иными словами - что k делает 2^k = n true? Вы можете просмотреть, что вы знаете о логарифмах.

источник

2016-01-20 02:08:14

Первое: у вас почти точно (N x N/2/2) операции, поэтому это O (N^2). Нарисуйте квадрат: вы увидите, что вы берете один треугольник (и один случай над двумя).

Во-вторых: у вас есть операции log2 N, поэтому это O (log N).

источник

2016-01-21 07:54:08

Чтобы понять проблему 2, вы можете имитировать пример. И если вы пишете цифры в двоичной базе, все должно стать очевидным:

100 -> 1100100 
50 -> 110010 
25 -> 11001 
12 -> 1100 
    6 ->  110 
    3 ->  11 
    1 ->  1

источник

2016-01-21 07:59:09

Продолжительность программ

ответ

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