Время работы алгоритма и оценка его сложности

[Invisible]

Надо определить время работы алгоритма и оценить его сложность
Я под каждым примером написал ответы которые у меня получились
проверьте плиз правильно или нет =)

1.For I = 1: N 
  I=I+1;     
  For K=1:N
      K=K+1;
  End  
End

\Longrightarrow n^2, O(n^2)

2. For I = 1: N 
  I=I*2;     
  For K=1:N
      K=K+1;
  End  
End 

\Longrightarrow \frac {n^2} {2} , O(n^2)

3. For I = 1: N 
  I=I*2;     
  For K=1:N
      K=K*2;
  End  
End 

\Longrightarrow \frac {n^2} {4} , O(n^2)

4. For I = 1: N 
  I=I+1;     
  For K=1:I
      K=K+1;
  End  
End  

\Longrightarrow \frac {n+n^2} {2} , O(n^2)

5. For I = 1: N 
  I=I*2;     
  For K=1:I
      K=K+1;
  End  
End 

\Longrightarrow 2^n-1 , O(2^n) - ??? неуверен

 
6. For I = 1: N 
  I=I*2;     
  For K=1:I
      K=K*2;
  End  
End 

\Longrightarrow \frac {n+n^2} {2} , O(n^2)

[maxal]

Во втором примере внешний цикл крутится $1+\lfloor\log_2 N\rfloor$ раз и ответом будет $O(N\log N)$. В остальных аналогичных задачах у вас также неверные ответы.

[Invisible]

maxal спасибо, а можешь посоветовать литературу по данной теме ?

а то я запутался

вроде по моей формуле работает
например во втором примере если \begin{verbatim} N=4\end{verbatim}
то \begin{verbatim} I \end{verbatim} и\begin{verbatim} K \end{verbatim} примут значения:

\begin{verbatim} I - K 1 - 2 - 1 2 4 - 1 2 3 4 \end{verbatim}

тоесть в сумме будет 7 действий
как раз по формуле $ \frac {n^2} 2 -1 $

[незваный гость]

Invisible, Вы, к сожалению, не указали язык. Между тем, это существенно — в некоторых языках конструкция

For I = 1:5
  I = I * I
  Print I
End

напечатает 1, 4, 9, 16, 25, а не 1, 4, 16.

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

P.S. Вы нашли необычный способ записи кода. Форум предоставляет другой — тег [code]

[Invisible]

незваный гость писал(а):

Вы, к сожалению, не указали язык.

сори,
актуально для языка С++
запись в виде псевдо кода

незваный гость писал(а):

P.S. Вы нашли необычный способ записи кода. Форум предоставляет другой — тег [code]

исправил

[незваный гость]

Invisible писал(а):

актуально для языка С++
запись в виде псевдо кода

тогда maxal прав.

Invisible писал(а):

исправил

Немного жаль. Ваш способ был удобочитаем, но очень необычен. Хорошо хоть, кусочек остался, как пример «хорошей магии»


~~~

Ещё одна деталь: какие операции Вы считаете? Сложения, умножения, или число исполнений внутреннего цикла? Если последнее, то нехитро модифицировать любую из программ примерно так:

5.ExecutionCount = 0;
For I = 1: N
  I=I*2;     
  For K=1:I
      K=K+1;
      ++ExecutionCounter;
  End 
End
Print(N, ExecutionCounter);

и сверить с ответом для $N = 1, 2, 3,…$. Думаю, дойдя до 10, Вы найдёте либо совпадение, либо ошибку в большинстве случаев.

[Invisible]

незваный гость писал(а):

Немного жаль. Ваш способ был удобочитаем, но очень необычен. Хорошо хоть, кусочек остался, как пример «хорошей магии»

вы сами попросили
мне тоже нравилось больше как было

незваный гость писал(а):

Ещё одна деталь: какие операции Вы считаете? Сложения, умножения, или число исполнений внутреннего цикла? Если последнее, то нехитро модифицировать любую из программ примерно так:

считать надо по внутреннему циклу
сделать программу и тупо посмотреть на то сколько получится не сложно
вопрос в том как правильно формулу написать

есть литература по теме?

[незваный гость]

Invisible писал(а):

вы сами попросили Smile

Я не то, чтобы просил — просто сказал о возможности форума.

Invisible писал(а):

сделать программу и тупо посмотреть на то сколько получится не сложно

Конечно. Смысл в том, чтобы проверить формулу.

С ходу в голову приходит классика: например, первый том Кнута (Искусство программирования для ЭВМ). Но там это не очень внятно, как, впрочем, многое у К. У него же есть очень старая статья, предлагающая $\Theta$ нотацию.

Идея-то, в общем проста: честно считаем важные операции и находим асимптотику. $O$ идёт из классического матана, ничего специфически-алгоритмического нет. Есть пара приёмов: например, часто сумму оценивают интегралом.

Кстати, о честном подсчёте.

maxal писал(а):

Во втором примере внешний цикл крутится $1+\lfloor\log_2 N\rfloor$ раз

и это не совсем точно. Асимптотически, пожалуй, верно, но тогда слишком деталей — можно просто $\log_2 N$ написать. А точную формулу дать вряд ли удастся: здесь смешиваются сложение и умножение, а это часто плохо. Просто достаточно написать рекуррентную формулу для $I$ на очередной итерации: $I_1 = 1, I_j = I_{i-1}^2+1$. Вот этот-то $+1$ всё и портит: последовательность растёт несколько быстрее, чем проcто $2^{j-1}$.

[maxal]

незваный гость писал(а):

Вот этот-то $+1$ всё и портит

А кто сказал, что там инкремент переменной происходит? Как я понял, "For" задает просто начальное значение и интервал для переменной цикла, а изменение переменной - уже где-то внутри. Типа как C++:

for(int i=1;i<=N;i=i*2)

Если именно такая конструкция имется в виду, то мой подсчет количества итераций точен.

[незваный гость]

maxal писал(а):

А кто сказал, что там инкремент переменной происходит?

Никто не сказал. Именно поэтому я писал о семантике языка. Но я ещё не встречал языка с FOR, указывающим пределы и не изменяющим переменную цикла по некоторым правилам (или, по крайней мере, явно не отменяющего изманение). Поэтому я подразумевал конструкцию типа:

for (i = 1; i <= N; ++i) {
  i = i * 2;
  …
}

Эх, стереотипы, стереотипы… Я тоже попался на эту удочку.

[Invisible]

maxal писал(а):

незваный гость писал(а):

Вот этот-то $+1$ всё и портит

А кто сказал, что там инкремент переменной происходит? Как я понял, "For" задает просто начальное значение и интервал для переменной цикла, а изменение переменной - уже где-то внутри. Типа как C++:

for(int i=1;i<=N;i=i*2)

У меня в условии не сказано на счет значения
но мне кажется что

 For I = 1: N
  I=I*2;  
End

надо считать так:

for(int i=1;i<=N;i=i*2)

maxal писал(а):

Если именно такая конструкция имется в виду, то мой подсчет количества итераций точен.

если подставить N = 32
то получится что во втором примере внешний цикл крутится $\log_2 N$а не $1+\lfloor\log_2 N\rfloor$
так как I примит значения: 2 4 8 16 32
тоесть 5 значний => $\log_2 32 = 5$

или я ошибаюсь?

[maxal]

Invisible писал(а):

если подставить N = 32
то получится что во втором примере внешний цикл крутится $\log_2 N$а не $1+\lfloor\log_2 N\rfloor$
так как I примит значения: 2 4 8 16 32

Еще $I=1$. Всего 6.

[Invisible]

maxal писал(а):

Invisible писал(а):

если подставить N = 32
то получится что во втором примере внешний цикл крутится $\log_2 N$а не $1+\lfloor\log_2 N\rfloor$
так как I примит значения: 2 4 8 16 32

Еще $I=1$. Всего 6.

но если считать количество выполнений внутреннего цикла, который зависит от внешнего
то выходит что 5 * 32 ...?

Добавлено спустя 2 часа 18 минут 27 секунд:

Проверьте плиз, правильно ли я сейчас подсчитал время работы алгоритма и его сложность

1.For I = 1: N 
  I=I+1;     
  For K=1:N
      K=K+1;
  End  
End

\Longrightarrow n^2, O(n^2)

2. For I = 1: N 
  I=I*2;     
  For K=1:N
      K=K+1;
  End  
End 

\Longrightarrow $(N-1)*(\log_2 N)$ , O($N*(\log N)$)

3. For I = 1: N 
  I=I*2;     
  For K=1:N
      K=K*2;
  End  
End 

\Longrightarrow $(\log_2 N)*(\log_2 N)$ , O((\log N)^2)

4. For I = 1: N 
  I=I+1;     
  For K=1:I
      K=K+1;
  End  
End  

\Longrightarrow \frac {n^2-n} {2} , O(n^2)

5. For I = 1: N 
  I=I*2;     
  For K=1:I
      K=K+1;
  End  
End 

\Longrightarrow $2^\log_2 N +1$-2 -$\log_2 N$ , O($2^\log N$)

 
6. For I = 1: N 
  I=I*2;     
  For K=1:I
      K=K*2;
  End  
End 

\Longrightarrow \frac {(\log_2 N ) +(\log_2 N )^2} {2} , O((\log N)^2)

[Invisible]

народ проверьте плиз правильность моего решения