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

@Кансег · Регистрация: 09.01.2013

Author24 — интернет-сервис помощи студентам

Pascal

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.
Подскажите правильно ли так определять верхнюю оценку?
Спасибо.

@Shamil1 · 14.05.2017, 23:29

Сообщение от arts1

1. Есть два односвязных списка с N и M элементами. Надо найти сложность нахождение такого двусвязного списка, где есть только те элементы N, которые присущы в M? Вроде O(M*N), но двусвязность кажется это усложняет?

O(M logM + N logN)

@arts1 · 15.05.2017, 01:16

Обьяснить можете касательно такой "сложной сложности". Почему там дважды logK - сортировки там не надо. И насколько помню такого варианта не было? А если б надо было создать односвязный результирующий список? О(M*N).

@Shamil1 · 15.05.2017, 15:43

Сообщение от arts1

Обьяснить можете касательно такой "сложной сложности". Почему там дважды logK - сортировки там не надо.

Если нужно слить два списка, то быстрее будет их сначала отсортировать.

з.ы. Теоретически, задачу можно сделать за O(N + M), если тупо пройтись по спискам, добавляя их элементы в HashTable... но нужна хорошая Hash функция, чтобы добавление работало за О(1)... то есть, некая зависимость от типа данных.

@arts1 · 17.05.2017, 00:46

Да не надо так складно -- если для создание односвязного списка сложность O(N*logN+M*logM),
то для придание ему двусвязности, согласно этому коду https://www.quora.com/How-do-y... ist-in-C++, надо лиш лишний проход в количестве M (длина конечного списка может быть иной)-->O(N*logN+M*logM+M)?

@Shamil1 · 17.05.2017, 16:44

Сообщение от arts1

O(N*logN+M*logM+M)?

так как M*logM >= M, это можно упростить до O(N*logN+M*logM)

@arts1 · 17.05.2017, 20:33

Ну если M*logM ---> M , то тогда вообще формулу можно упростить к O(M+N+M), что наверное неправильно.

@Shamil1 · 17.05.2017, 21:16

Сообщение от arts1

Ну если M*logM ---> M

Не "M*logM ---> M", а "M*logM больше или равно M"

Добавлено через 1 минуту
Аналогично O(x² + x) = O(x²)

@arts1 · 17.05.2017, 23:09

Да я понял. Через минуту-две спохватился что написал, а что вами имелось ввиду.

Добавлено через 5 минут
Думаю самый простой вопрос на тему. Сложность нахождение студента в студенческом журнале -- logN, если учесть что список уже отсортирован по алфавиту? И применим бинарный поиск.

@Shamil1 · 18.05.2017, 00:44

Сообщение от arts1

Сложность нахождение студента в студенческом журнале -- logN, если учесть что список уже отсортирован по алфавиту?

Да, если есть доступ по индексу за O(1).

@arts1 · 27.09.2017, 14:04

Тут здесь еще таких два примера появилось, которые у меня представляются со сложностью O(1): первое задание это получение следующего элемента односвязного списка (очереди), и вставка М значений в hash-table? Хотя в первом случае очевидно что значение доступа в общем случае O(n).

@Shamil1 · 27.09.2017, 18:49

Следующий элемент: O(1).
Вставка М значений в hash-table: O(М).

@arts1 138 / 7 / 1 Регистрация: 31.03.2015 Сообщений: 395
	15.05.2017, 01:16	22
	Обьяснить можете касательно такой "сложной сложности". Почему там дважды logK - сортировки там не надо. И насколько помню такого варианта не было? А если б надо было создать односвязный результирующий список? О(M*N). 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,469
	17.05.2017, 16:44	25
	Сообщение от arts1 O(NlogN+MlogM+M)? так как MlogM >= M, это можно упростить до O(NlogN+M*logM) 0

@arts1 138 / 7 / 1 Регистрация: 31.03.2015 Сообщений: 395
	17.05.2017, 20:33	26
	Ну если M*logM ---> M , то тогда вообще формулу можно упростить к O(M+N+M), что наверное неправильно. 0

@arts1 138 / 7 / 1 Регистрация: 31.03.2015 Сообщений: 395
	17.05.2017, 23:09	28
	Да я понял. Через минуту-две спохватился что написал, а что вами имелось ввиду. Добавлено через 5 минут Думаю самый простой вопрос на тему. Сложность нахождение студента в студенческом журнале -- logN, если учесть что список уже отсортирован по алфавиту? И применим бинарный поиск. 0

@arts1 138 / 7 / 1 Регистрация: 31.03.2015 Сообщений: 395
	27.09.2017, 14:04	30
	Тут здесь еще таких два примера появилось, которые у меня представляются со сложностью O(1): первое задание это получение следующего элемента односвязного списка (очереди), и вставка М значений в hash-table? Хотя в первом случае очевидно что значение доступа в общем случае O(n). 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,469
	14.05.2017, 23:29	21
	Сообщение от arts1 1. Есть два односвязных списка с N и M элементами. Надо найти сложность нахождение такого двусвязного списка, где есть только те элементы N, которые присущы в M? Вроде O(M*N), но двусвязность кажется это усложняет? O(M logM + N logN) 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,469
	15.05.2017, 15:43	23
	Сообщение от arts1 Обьяснить можете касательно такой "сложной сложности". Почему там дважды logK - сортировки там не надо. Если нужно слить два списка, то быстрее будет их сначала отсортировать. з.ы. Теоретически, задачу можно сделать за O(N + M), если тупо пройтись по спискам, добавляя их элементы в HashTable... но нужна хорошая Hash функция, чтобы добавление работало за О(1)... то есть, некая зависимость от типа данных. 0

@arts1 138 / 7 / 1 Регистрация: 31.03.2015 Сообщений: 395
	17.05.2017, 00:46	24
	Да не надо так складно -- если для создание односвязного списка сложность O(NlogN+MlogM), то для придание ему двусвязности, согласно этому коду https://www.quora.com/How-do-y... ist-in-C++, надо лиш лишний проход в количестве M (длина конечного списка может быть иной)-->O(NlogN+MlogM+M)? 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,469
	17.05.2017, 21:16	27
	Сообщение от arts1 Ну если MlogM ---> M Не "MlogM ---> M", а "MlogM больше или равно M" Добавлено через 1 минуту* Аналогично O(x² + x) = O(x²) 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,469
	18.05.2017, 00:44	29
	Сообщение от arts1 Сложность нахождение студента в студенческом журнале -- logN, если учесть что список уже отсортирован по алфавиту? Да, если есть доступ по индексу за O(1). 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,469
	27.09.2017, 18:49	31
	Следующий элемент: O(1). Вставка М значений в hash-table: O(М). 0