Форум программистов, компьютерный форум CyberForum.ru

Асимптотический анализ алгоритмов - C++

Восстановить пароль Регистрация
 
Mobalis
Сообщений: n/a
19.10.2012, 01:57     Асимптотический анализ алгоритмов #1
Здравствуйте. Помогите разобраться, что такое асимптотический анализ алгоритмов. Я мало что помню из школьной программы, поэтому сейчас приходится читать википедию и учить все заново, да и в программировании я новичок. Возникает много вопросов. Сейчас пытаюсь понять статью на хабре

Начну с определения:
Запись вида f(n) = O(g(n)) означает, что ф-ия f(n) возрастает медленнее чем ф-ия g(n) при с = с1 и n = N, где c1 и N могут быть сколь угодно большими числами, т.е. При c = c1 и n >= N, c*g(n) >=f(n).

1)Что такое c, c1 и N?
Читая дальше, я начал догадываться, что c и c1 это количество операций в циклах в func1() и fucn2() так ли это?

2)Как я понял,
C++
1
2
3
func()
    for(;i <= 10; ++i)
        for(;j <= 10; ++j)
Имеет сложность n^n, т.е. 10^10 ?

3)Если c = количеству операций во вложенном цикле, то
C++
1
2
3
4
5
6
7
8
func2()
   for(;i <= 10; ++i)
       for(;j <= 10; ++j)
       {
           int a = j;
           int b = a;
           int c = a + b;
       }
Будет иметь сложность 4*func2(10^10) ?

4)
C++
1
2
3
4
5
func3()
   for(int i; i <= 10; ++i)
       int a = i * i * i;
   for(int j; j <= 10; ++j)
       int b = j * j * j;
Какую сложность имеет функция? 3*fucn3(2*n) ?

Кажется я окончательно запутался и пишу бред. Если есть время и возможность, помогите на пальцах понять, хотя бы азы асимптотического анализа. Спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.10.2012, 01:57     Асимптотический анализ алгоритмов
Посмотрите здесь:

Оптимизация алгоритмов C++
C++ Комбинирование алгоритмов.
С++/алгоритм/Тема:"Анализ производительности алгоритмов" C++
C++ Анализ алгоритмов поиска
Распараллеливание алгоритмов C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Jupiter
Каратель
Эксперт C++
6543 / 3963 / 226
Регистрация: 26.03.2010
Сообщений: 9,273
Записей в блоге: 1
Завершенные тесты: 2
19.10.2012, 04:04     Асимптотический анализ алгоритмов #2
Цитата Сообщение от Mobalis Посмотреть сообщение
2)Как я понял,
C++
1
2
3
func()
* * for(;i <= 10; ++i)
* * * * for(;j <= 10; ++j)
Имеет сложность n^n, т.е. 10^10 ?
n зависит от начальных значений i, j
10 раз да по 10 = 10 * 10 = 10 ^ 2 (при i = j = 1)
Mobalis
Сообщений: n/a
19.10.2012, 17:47     Асимптотический анализ алгоритмов #3
Да Вы правы, я все напутал когда писал, хотя в голове имел правильное представление.
Но ответьте пожалуйста.
C++
1
2
3
4
5
6
7
func3()
   {
   for(int i = 0; i < 10; ++i)
       int a = i * i * i;
   for(int j = 0; j < 10; ++j)
       int b = j * j * j;
   }
Сложность fucn3() = О(n*2)?
При записи сложности, мы учитываем количество операций внутри цикла? Или только обращаем внимание на циклы?
Герц
523 / 340 / 4
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
19.10.2012, 17:49     Асимптотический анализ алгоритмов #4
Временная сложность последней функции - O(n)
Yandex
Объявления
19.10.2012, 17:49     Асимптотический анализ алгоритмов
Ответ Создать тему
Опции темы

Текущее время: 09:31. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru