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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Mobalis
Сообщений: n/a
#1

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

19.10.2012, 01:57. Просмотров 1006. Ответов 3
Метки нет (Все метки)

Здравствуйте. Помогите разобраться, что такое асимптотический анализ алгоритмов. Я мало что помню из школьной программы, поэтому сейчас приходится читать википедию и учить все заново, да и в программировании я новичок. Возникает много вопросов. Сейчас пытаюсь понять статью на хабре

Начну с определения:
Запись вида 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++
почему для этого примера: tmp = a; a = b; b = tmp; О-нотация равна O(1), а не O(3) или для этого примера S = 1 + 2 + 3 + .. n =...

Анализ алгоритмов поиска - C++
Написать программу, в которой используются четыре метода поиска: 1. Линейный поиск в массиве. 2. Бинарный поиск в заранее...

Сравнительный анализ алгоритмов сортировки - C++
Помогите пожалуйста реализовать программу для сравнения алгоритмов сортировок. Нужно отдельно программу для внутренних сортировок. И...

С++/алгоритм/Тема:"Анализ производительности алгоритмов" - C++
Преобразовать одномерный массив,состоящий из n целых элементов,таким образом,чтобы сначала располагались все положительные элементы,а потом...

Программирование алгоритмов - C++
я с С++ знаком не давно, решил заняться лабами, всё вроде бы хорошо, но вот одна попалась не понятная) Вообщем нужно написать...

Распараллеливание алгоритмов - C++
Доброго дня всем. Встал вопрос о выборе темы,связанной с распараллеливанием алгоритмов. Какие задачи наиболее &quot;восприимчивы&quot; к...

3
Jupiter
Каратель
Эксперт С++
6556 / 3977 / 227
Регистрация: 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)
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)?
При записи сложности, мы учитываем количество операций внутри цикла? Или только обращаем внимание на циклы?
Герц
524 / 341 / 4
Регистрация: 05.11.2010
Сообщений: 1,077
Записей в блоге: 1
19.10.2012, 17:49 #4
Временная сложность последней функции - O(n)
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.10.2012, 17:49
Привет! Вот еще темы с ответами:

Ускорение алгоритмов - C++
Имеется код, нужно его ускорить. (Помогите тупому!!!!!!!) #include &lt;stdio.h&gt; #include &lt;iostream&gt; #include &lt;string&gt; #include...

Комбинирование алгоритмов. - C++
помогите плз , с задачей непойму чтот нитак сделано походу )) Условие : Если сумма трех попарно различных действительных чисел x, y,...

5 алгоритмов сортировки - C++
Ребят,помогите с курсовой по программированию,пожалуйста.Нужно создать матрицу(с помощью векторов,рандомную),посчитать умножение елементов...

Сложность алгоритмов - C++
Добрый день, пытаюсь оценить сложность алгоритмов, но возникли сомнения в правильности рассчетов. Собственно рассматриваю два алгоритма -...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Yandex
Объявления
19.10.2012, 17:49
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru