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

Анализ алгоритмов - C++

Восстановить пароль Регистрация
 
Page
0 / 0 / 0
Регистрация: 03.05.2013
Сообщений: 49
11.12.2013, 04:43     Анализ алгоритмов #1
почему для этого примера:
tmp = a;
a = b;
b = tmp;
О-нотация равна O(1), а не O(3)
или для этого примера
S = 1 + 2 + 3 + .. n = n(n + 1)/2
тоже равняется O(1)???
в книге слишком заумно объяснили
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2013, 04:43     Анализ алгоритмов
Посмотрите здесь:

Оптимизация алгоритмов C++
C++ Комбинирование алгоритмов.
С++/алгоритм/Тема:"Анализ производительности алгоритмов" C++
C++ Анализ алгоритмов поиска
Распараллеливание алгоритмов C++
C++ Асимптотический анализ алгоритмов
C++ Программирование алгоритмов
C++ Ускорение алгоритмов

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
el_gato_de_Ch
35 / 35 / 1
Регистрация: 28.04.2013
Сообщений: 110
11.12.2013, 06:49     Анализ алгоритмов #2
O(1) 1 не означает число выполняемых операций. оно означает, что время постоянно, оно не зависит от числа вводимых операций.
в первом примере функции swap при любом значении вводимых данных, программа выполнит только 3 операции, не больше и не меньше.
во втором примере, сумма считается формулой, поэтому программа, в этом случае тоже выполнит только 5(точно не могу сказать) операций, хоть n = 5, хоть n = 10000,

если во втором примере формулу заменить циклом for и считать сумму напрямую складывая члены прогрессии, то сложность станет O(n) потому что в этом случае число операций, выполняемых программой, сразу станет пропорционально вводимому числу n, так при n = 5, он выполнит 5 сложений, а при n = 1000 он выполнить 1000,

O(f(n)) это есть асимптотическая сложность алгоритма, не путай её с временной функцией выполнения t(f(n))
Yandex
Объявления
11.12.2013, 06:49     Анализ алгоритмов
Ответ Создать тему
Опции темы

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