Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.59/22: Рейтинг темы: голосов - 22, средняя оценка - 4.59
Кансег
0 / 0 / 1
Регистрация: 09.01.2013
Сообщений: 41
1

Определение временной сложности алгоритма (О символика)

20.10.2013, 23:10. Просмотров 4616. Ответов 30
Метки нет (Все метки)

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Procedure R(n, x : integer); 
Var i, j :integer;
begin
  S:=0; 
  For i:=1 to 2*n do
    if a[i] > х then
           For j:=1 to n*n do
             s:=s+A[j];
end;
{основная прога}
Var t, u : integer;
begin 
{1}  for q:=1 to 10 do begin R(5, q)
{2}   for t:=1 to 20 do R(2*t, q); 
  end;
End;
Сама процедура у меня получилась имеет O=n^3, (вложенный цикл{2} равен 2n^3 и верхний{1} равен n^3) и в итоги алгоритм О=2n^6=n^6.
Подскажите правильно ли так определять верхнюю оценку?
Спасибо.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.10.2013, 23:10
Ответы с готовыми решениями:

О символика (определение временной сложности алгоритма)
S:=0; For i:=1 to n*2 do begin s:=s+A; For j:=1 to n - 2 do begin s:=s+A; For k:=1 to n-3 do...

Определение сложности алгоритма / Pascal
Доброго времени суток. Есть такой код: type mas = array of integer; procedure InsertSort(var...

Анализ сложности алгоритмов. О-символика
Помогите разобраться. Нашел функцию f(n) алгоритма, допустим, 5n2+3n+4. Как найти О большое знаю,...

Временной порядок сложности "пузырька"
Сложность алгоритма: O \left({n}^{2} \right) вопрос что это значит? и что за переменные O и n ?

Оценка сложности алгоритма
Здравствуйте, уважаемые форумчане! Появилась необходимость оценки временной сложности алгоритма...

30
Mysterious Light
Эксперт по математике/физике
4094 / 2003 / 410
Регистрация: 19.07.2009
Сообщений: 3,022
Записей в блоге: 22
21.10.2013, 01:40 2
Временная сложность — это зависимость времени от некоторого параметра. Что является этим параметром?
У R понятно, есть n и x, притом время зависит от n как O(n^3).
А основная программа зависит от чего? Здесь ничего не считывается из stdin, нет никаких чётко-обозначенных констант, которые можно бы проварьировать. Короче, от чего время выполнения зависит?
В приведённом виде программа отрабатывает всегда одинаковое время, а поэтому её временная сложность O(1).
1
Кансег
0 / 0 / 1
Регистрация: 09.01.2013
Сообщений: 41
21.10.2013, 01:57  [ТС] 3
Mysterious Light, Эм было 2 задания по одному коду, объединил...
1.(Относится к процедуре) Определите функцию роста f(N) трудоемкости данного алгоритма и её асимптотические оценки ( f(N)), O(f(N)), ( f(N)), o(f(N)), ( f(N)), где N – длина входа.
2. (Относится к основному алгоритму программы) Вычислите функцию роста f(N) трудоемкости данного алгоритма с учетом фактического числа инструкций, исполняемых при выполнении функции, анализ трудоемкости и расчет f(n) которой был Вами выполнен в пред. задании.
Эм, загнул я с оценкой времени... нужна общая функция роста, а у меня более-менее, только с верхней оценкой))
Спасибо.
0
arts1
135 / 4 / 1
Регистрация: 31.03.2015
Сообщений: 346
12.09.2016, 20:05 4
Чтобы не создавать новую тему задам подобный вопрос здесь: какая сложность алгоритма определение М-ного наименьшего из списка из N-элементов? M*N?
0
12.09.2016, 20:05
Shamil1
Модератор
2292 / 1589 / 354
Регистрация: 26.03.2015
Сообщений: 5,772
12.09.2016, 21:35 5
O (N)
0
arts1
135 / 4 / 1
Регистрация: 31.03.2015
Сообщений: 346
12.09.2016, 22:39 6
Так просто? Это когда найти наименьший/наибольший элемент. А это надо 2ой, 3ий наименьший элемент. Где то методом сортировки написано что вообще - N*logN. От M то должно зависить.
0
Shamil1
Модератор
2292 / 1589 / 354
Регистрация: 26.03.2015
Сообщений: 5,772
13.09.2016, 12:37 7
Цитата Сообщение от arts1 Посмотреть сообщение
Так просто?
Алгоритм похож на алгоритм быстрой сортировки. Отличие в том, что продолжать работать нужно только с нужной частью массива.
Такой алгоритм даёт O(N) в среднем. (Быстрая сортировка даёт O(N*logN) в среднем).

Существует алгоритм, который даёт O(N) в худшем случае, но он представляет чисто теоретический интерес.

з.ы. На случай, если Вы хотите найти в интернете подробное описание и/или реализацию: задача называется "Порядковые статистики".

Добавлено через 3 минуты
Анализ времени работы:
http://neerc.ifmo.ru/wiki/index.php?...B8%D0%BA%D0%B8
0
arts1
135 / 4 / 1
Регистрация: 31.03.2015
Сообщений: 346
14.09.2016, 16:45 8
Я вот не понимаю почему в расчете сложности алгоритмов часто применяют log N, почему за основание берут 10. Понимаю некое пояснение логарифмизации вычисление сложности алгоритмов для бинарного дерева, если log2 N.
0
Shamil1
Модератор
2292 / 1589 / 354
Регистрация: 26.03.2015
Сообщений: 5,772
14.09.2016, 18:02 9
Цитата Сообщение от arts1 Посмотреть сообщение
Я вот не понимаю почему в расчете сложности алгоритмов часто применяют log N, почему за основание берут 10.
Все логорифмы одинаковы... с точностью до константы. Поэтому берут просто "логарифм", не задумываясь, какое там основание.
0
oldnewyear
419 / 416 / 158
Регистрация: 21.05.2016
Сообщений: 1,325
15.09.2016, 15:27 10
Цитата Сообщение от Shamil1 Посмотреть сообщение
Алгоритм похож на алгоритм быстрой сортировки. Отличие в том, что продолжать работать нужно только с нужной частью массива.
Такой алгоритм даёт O(N) в среднем. (Быстрая сортировка даёт O(N*logN) в среднем).
https://en.wikipedia.org/wiki/Quickselect
0
Shamil1
Модератор
2292 / 1589 / 354
Регистрация: 26.03.2015
Сообщений: 5,772
15.09.2016, 18:11 11
Цитата Сообщение от oldnewyear Посмотреть сообщение
https://en.wikipedia.org/wiki/Quickselect
А зачем мне эта ссылка? Раз я пишу про быструю сортировку, я знаю, что это такое.
1
oldnewyear
419 / 416 / 158
Регистрация: 21.05.2016
Сообщений: 1,325
16.09.2016, 00:31 12
Цитата Сообщение от Shamil1 Посмотреть сообщение
А зачем мне эта ссылка? Раз я пишу про быструю сортировку, я знаю, что это такое.
Просто добавил ссылку с описанием упомянутого вами алгоритма. Может, кому то будет полезно
0
arts1
135 / 4 / 1
Регистрация: 31.03.2015
Сообщений: 346
17.09.2016, 21:59 13
Уже писал: но log2 N, log N, ln N, где например N=100, это разные числа. Или O-нотация это чисто индикативный показатель? Например использование О-нотации к определение сложности алгоритма односвязного списка (или его сортировки) не совсем понятна. Где там варианты выбора, как в бинарном дереве- ведь там сложность тоже с помощью логарифма N определяется?
0
Shamil1
Модератор
2292 / 1589 / 354
Регистрация: 26.03.2015
Сообщений: 5,772
17.09.2016, 22:10 14
Цитата Сообщение от arts1 Посмотреть сообщение
но log2 N, log N, ln N, где например N=100, это разные числа
Эти фукции одинаковы с точностью до постоянного множителя.
log2 N = log10 N / log10 2
отсюда
log2 N = C * log10 N

Цитата Сообщение от arts1 Посмотреть сообщение
алгоритма односвязного списка (или его сортировки)
какого именно алгоритма?
0
arts1
135 / 4 / 1
Регистрация: 31.03.2015
Сообщений: 346
16.03.2017, 00:10 15
Вот еще один непонятный момент -- удаление или поиск в односвязном списке. Поиск -- там считается O(N), а доступ -- O(1) -- но именно последняя ціфра считается правильной? Интересный подход -- если указатель (итератор) находиться над необходимым элементом тогда и сложность искать не надо, но должно исходить из предположения что "указатель" есть в начале или вконце списка?
Как тогда быть из двусвязным списком (Linked List) -- O(N/2)= O(N)?
0
oldnewyear
419 / 416 / 158
Регистрация: 21.05.2016
Сообщений: 1,325
16.03.2017, 01:46 16
Цитата Сообщение от arts1 Посмотреть сообщение
Вот еще один непонятный момент -- удаление или поиск в односвязном списке. Поиск -- там считается O(N), а доступ -- O(1) -- но именно последняя ціфра считается правильной? Интересный подход -- если указатель (итератор) находиться над необходимым элементом тогда и сложность искать не надо, но должно исходить из предположения что "указатель" есть в начале или вконце списка?
Как тогда быть из двусвязным списком (Linked List) -- O(N/2)= O(N)?
удаление элемента из списка и поиск элемента - две разные операции, поэтому у каждой операции своя временная сложность. Двусвязный список позволяет добавлять в конец списка и удалять последний элемент списка за O(1), вот и вся разница
0
arts1
135 / 4 / 1
Регистрация: 31.03.2015
Сообщений: 346
16.03.2017, 03:19 17
Вот я и не помню речь шла о доступе (чтение) или удаление элемента или о двух операциях за O(1).
"Двусвязный список позволяет добавлять в конец списка и удалять последний элемент списка за O(1)" -- ну это понятно если иметь ввиду, что проход идет с двух концов -- но доступ к внутренним элементам быстрее то должно происходить...?
0
oldnewyear
419 / 416 / 158
Регистрация: 21.05.2016
Сообщений: 1,325
16.03.2017, 03:50 18
Цитата Сообщение от arts1 Посмотреть сообщение
Вот я и не помню речь шла о доступе (чтение) или удаление элемента или о двух операциях за O(1).
Удаление элемента, как примитивная операция имеет сложность O(1)
В свою очередь, алгоритм удаления элемента из списка включает две примитивные операции - поиск + удаление = O(n) + O(1) = O(n)

Цитата Сообщение от arts1 Посмотреть сообщение
но доступ к внутренним элементам быстрее то должно происходить...?
Не быстрее. Абсолютно так же. Нахождение элемента в двусвязном элементе неизвестно, поэтому чтобы его найти нужно перебрать все элементы начиная с первого, как и в односвязном списке
0
arts1
135 / 4 / 1
Регистрация: 31.03.2015
Сообщений: 346
07.04.2017, 22:14 19
O(1) -- как его можно удалить, если не найти сперва?
поэтому чтобы его найти нужно перебрать все элементы начиная с первого -- если уже нашел,
то может не надо продолжать перебор, даже если найденный элемент был первым или вторым при переборе?
Еще интересует такой момент -- мы как параметр при "нахождение" передаем этот обьект ("Type/Class" Objectname) -- по каким признакам система определяет что это именно Objectname?
0
arts1
135 / 4 / 1
Регистрация: 31.03.2015
Сообщений: 346
14.05.2017, 21:48 20
Вот у меня еще два примера нашлось, касательно комплексити.
1. Есть два односвязных списка с N и M элементами. Надо найти сложность нахождение такого двусвязного списка, где есть только те элементы N, которые присущы в M? Вроде O(M*N), но двусвязность кажется это усложняет?
2. Есть два масива (списка): упорядоченный из M элеметов, и неупорядоченный из N элементов. Надо найти сложность нахождение упорядоченного масива, где будет присущи все элементы двух масивов. Если взять за базовый -- передвижение по сортированому масиву M -- то тоже О(M*N), если -- не по сортированому N (N*logM), если использовать бинарный поиск по M.
0
14.05.2017, 21:48
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.05.2017, 21:48

Оценка сложности алгоритма!
пожалуйста выручите ) нужно оценить сложность алгоритма T(n)=3*(3/n)+n/log n

Оценка сложности алгоритма
1.for( i = 1 ; i < n ; i++){ }.. 2.for( i = 1 ; i <=n ; i++){ }.. 3. .for( i = 1 ; i <n-1...

Оценка сложности алгоритма
Подскажите какая сложность у данного алгоритма, искал в интернете что за алгоритм не нашел...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

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