Loop Iteration Analysis Part 2

Чтобы прояснить, прежде чем я начну, это НЕ домашнее задание, а скорее я изучаю для своего экзамена. Я дал решения по следующим вопросам. Я хотел бы получить конструктивную обратную связь.Loop Iteration Analysis Part 2

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

Найдите время работы в терминах обозначения O (n).

int y=0; 
for(int j=1; j*j<=n; j++)// runs from 1->j=sqrt(n) times 
    y++; //constant - c

Таким образом, время выполнения является c x n^1/2 = O(n^1/2)

Q2.

int b=0; 
for(int i=n; i>0; i--) //runs from n->1 
    for(int j=0; j<i; j++) // runs from 0 to i 
     b=b+5; //constant

для каждого значения j (1,2...,n) трасс внутреннего контура I раз постоянной = ci. - nc+(n-1)+...+2c+1c = c(n+..+2+1) = cn(n+1)/2 = O(n^2) время выполнения.

Q3.

int y=1; 
int j=0; 
for(j=1; j<=2n; j=j+2) //runs 2n times, increments by 2 
    y=y+i; //constant c 

int s=0; 
for(i=1; i<=j; i++) // not a nested for loop, therefore runs n times 
    s++;

Время работы: O(n)

Q4.

int x=0; //constant 
for(int i=1; i<=n; i=i*3) //runs log_3 (n) times 
{ 
    if(i%2 != 0) // for values above will always be 1 

    for(int j=0; j<i; j++) // runs from 0 to log_3(n) 
     x++; 
}

поэтому мы имеем clog_3(n)xclog_3(n) = O(log_3(n))^2

источник

2012-06-20 warpstar

Первые три - вне сомнения. Но четвертый ... Может быть не 'O (log_3 (n))^2', а' O (mlog_3 (n)) ', потому что внутренний цикл повторяется над' 0-m' (фактически '0-i') вместо '0-log3 (n)'. Я имею в виду, да, внутренний цикл проходит точно только «O (log_3 (n))' раз, но не из '0-log_3 (n)' наверняка. – gahcep

Поразмыслить немного? до сих пор путают. thx – warpstar

Q4 никогда не завершит свой путь (если n = 1), потому что 'i' всегда будет 1, так как' 1^3' = 1 –

Ok, первые три являются вне сомнения (я считаю, все правильно). Но с Q4 есть проблема.

Ваш ответ несколько неверен. Определенно, результат не O(log_3(n))^2. Корпус находится во внутреннем контуре, который соответствует точно только O(log_3(n)) раз. И не от 0-log_3(n), а от 0-m (где m явно коррелирует с i).

Предполагая, что все выше, я думаю, что правильный ответ O(mlog3(n)). Но если кто-то подумает, что я ошибся, пожалуйста, поправьте меня.

источник

2012-06-20 03:37:17 gahcep

The loops can be thought of as two summations 

Summation (i from 1 to lg_3(n)) * Summation (j = 0 to i-1) [1 operation] 
= Summation (i = 1 to lg_3 (n) (i) 
= 1 + 2 + 3....lg_3(n) terms 
= lg_3(n) [ lg_3(n) + 1] /2 
= O (lg_3(n)] ^2

источник

2013-02-10 01:14:58

Loop Iteration Analysis Part 2

ответ

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