Перейти к содержимому

Фото
- - - - -

Посчитать количество выполнений команды

алгоритмы

  • Вы не можете создать новую тему
  • Please log in to reply
4 ответов в этой теме

#1 JakeTheFIsh

JakeTheFIsh
  • Пользователь
  • 629 сообщений

Отправлено 13 Февраль 2013 - 14:12

Всем привет!

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


int sum = 0;
for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
        for (int k = 1; k <= N; k = k*2)
            for (int h = 1; h <= k; h++)
                sum++;

Первых два цикла - N^2.
Третий по моим предположениям дает LOG2(N) + 1 или тоже самое что LOG2(2N)
Четвертый дает 2^(LOG2(N) + 1) - 1 или 2^(LOG2(2N)) - 1, если верить старым знаниям то это всё равняется 2N - 1

В итоге при перемножении выходит что можно на всё забить и останется только n^3.

Так ли?
  • 0
Есть три способа отвечать на вопросы: сказать необходимое, отвечать с приветливостью и – наговорить лишнего
Плутарх - (ок. 46 — ок.120) - древнегреческий писатель, историк

#2 Вырвиглаз

Вырвиглаз

    Убийца травы

  • Постоялец
  • 15 502 сообщений
  • Откуда:Эстония, Таллин

Отправлено 13 Февраль 2013 - 14:20

последняя выполняется k раз
далее LOG2(N)
далее N
и первая N
итого sum=k*(LOG2(N))*N^2

Сообщение изменено: Вырвиглаз (13 Февраль 2013 - 14:20 )

  • 0
Кто живет и грешит в Эстонии, тот опять родится в Эстонии.

#3 JakeTheFIsh

JakeTheFIsh
  • Пользователь
  • 629 сообщений

Отправлено 13 Февраль 2013 - 14:30

последняя выполняется k раз
далее LOG2(N)
далее N
и первая N
итого sum=k*(LOG2(N))*N^2

Это супер, а как выразить к через N?

Написал тестовый скрипт, проверить своё предположение. В итоге выкинул 3 цикл из расчетов - пока не понял почему, но он учитывается в четвертом.
В итоге получилось следующее:

N ^2 * (2*N - 1)
Если раскрыть скобки, то получится
N^3 - N^2
Что в принципе ~N^3.
Но это пока что гипотеза.
  • 0
Есть три способа отвечать на вопросы: сказать необходимое, отвечать с приветливостью и – наговорить лишнего
Плутарх - (ок. 46 — ок.120) - древнегреческий писатель, историк

#4 Вырвиглаз

Вырвиглаз

    Убийца травы

  • Постоялец
  • 15 502 сообщений
  • Откуда:Эстония, Таллин

Отправлено 13 Февраль 2013 - 14:35

Последний цикл крутится до h <= k, предыдущий завершается на k = n
Вообще ну нафиг голову ломать над школьными алгоритмами.
  • 0
Кто живет и грешит в Эстонии, тот опять родится в Эстонии.

#5 JakeTheFIsh

JakeTheFIsh
  • Пользователь
  • 629 сообщений

Отправлено 13 Февраль 2013 - 15:03

Последний цикл крутится до h <= k, предыдущий завершается на k = n

В принципе я также рассуждал. Но там получается так, что h связана с k через функцию, которую я написал уже %).

Я был прав : O(N^3)

Сообщение изменено: JakeTheFIsh (13 Февраль 2013 - 14:43 )

  • 0
Есть три способа отвечать на вопросы: сказать необходимое, отвечать с приветливостью и – наговорить лишнего
Плутарх - (ок. 46 — ок.120) - древнегреческий писатель, историк