Оценка сложности алгоритма

@qwesty_li · Регистрация: 02.05.2022

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

C++

void substr(string s, string sub)
{
    int n = 0, from =0;
    while ((n = s.find(sub, from)) != string::npos) 
    {
        cout << n << " ";
        from = n + sub.size();
    }
}

Здравствуйте, у нас тема оценки сложности алгоритма, алгоритм поиска подстроки в строке. Я написала вот такой, помогите пожалуйста определить его сложность.
В задании указано, что сложность определяется размером входящей строки и подстроки, которую нужно найти.

Спасибо))

@lemegeton · 18.05.2022, 00:37

Я фиг знает, какую сложность мы считаем. )))

Давайте "на глазок" худший случай.

Сложность std::string.find() не определяется стандартом. Будем считать, что она Na * Nb в худшем случае, как при ней написано.

Ваш алгоритм, без учёта сложности find(), в худшем случае отработает Na/Nb раз -- если Na будет полностью состоять из Nb.

С учётом сложности find(), ваш алгоритм нахождения всех подстрок в строке сделает (Na / Nb) * Na * Nb операций, что есть Na ^ 2.

Тут я, конечно, не учитываю, что обе эти ситуации худшего случая вместе скорее всего невозможны.

@_Ivana · 18.05.2022, 01:29

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

Я фиг знает, какую сложность мы считаем. )))

Когда-то давно, на форуме серьезных математиков, мне было достаточно забавно узнать, что при оценке "настоящей" сложности учитывается все, например операция сложения двух чисел имеет сложность не O(1) а O(log(n)), потому что именно столько бит требует их двоичное представление, и для больших чисел это важно

А то там были любители предложить алгоритмы проверки чисел на простоту асимптотически лучше известных, но после подобных уточнений все сразу вставало на свои места

А так, в рабоче-крестьянском смысле, все числа влезают в лонг лонг, складываются за O(1) и т.п. И жизнь вместе с оценкой такой "ненастоящей" сложности становится гораздо проще

@lemegeton · 18.05.2022, 01:42

"Серьезные математики" это такие дядьки, от которых хер чего добьешься, пока вопрос не будет сформулирован так, что ответ на него уже содержится в самом вопросе? )))

@_Ivana · 18.05.2022, 01:47

Именно так! Тем более, что на том форуме было строго контролируемое модераторами правило - бан падавану за отсутствие собственных попыток решения и бан отвечающим за решение "простых учебных задач" (в число коих входили, как вы понимаете, и не очень простые, в общепринятом смысле). Кстати, на этом благословенном форуме как минимум первая часть этих требований также отражена в правилах, но если бы они реально исполнялись, то вой разнесся бы по всему халяво-рунету, и местные админы потеряли бы траффик и доходы от рекламы, поэтому маемо шчо маемо (С)

@lemegeton · 18.05.2022, 15:23

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

не очень простые, в общепринятом смысле

Представляю, какие стандарты тривиальности имеют модераторы на форуме серьезных математиков.

Мат аппарат большинства программистов весьма скуден, особенно относительно "серьезных математиков".

Я тут час писал программку, считающую обратную матрицу.

А там всего-то пяток понятий.

А уж если надо тригонометрию порешать -- вэлкам ту гуголь.

Яб там с первого вопроса в баню ушёл.

Добавлено через 3 минуты

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

на этом благословенном форуме как минимум первая часть этих требований также отражена в правилах, но если бы они реально исполнялись, то вой разнесся бы по всему халяво-рунету, и местные админы потеряли бы траффик и доходы от рекламы, поэтому маемо шчо маемо (С)

Капитализм он такой.
Хотя я лично не возражаю.
Меня это развлекает и ЧСВ почесать приятно. Ну и потом, если бы я не решал эти студ задачки, уже сто раз бы забыл даже простейшую математику. )))
Да будет хватать местным админам на бутерброд с красной икрой во веки вечные.

@Kuzia domovenok · 18.05.2022, 16:02

_Ivana, каким макаром n означающее параметр алгоритма (мы же в каком-то алгоритме сложность оцениваем, например n - длина строки в этом посте) вдруг стало обозначать разрядность складываемых чисел? Вы же ссылаетесь на учёт алгоритмической сложности сложения в работе алгоритма поиска строк?
Типичное сложение тёплого с мягким. Если что у нас и складывается в программе, то явно в неизменных типах чисел и с неизменной сложностью процесса сложения, какие бы строки на входе не были!

@lemegeton 4773 / 2582 / 894 Регистрация: 29.11.2010 Сообщений: 5,590
	18.05.2022, 00:37	2
	Я фиг знает, какую сложность мы считаем. ))) Давайте "на глазок" худший случай. Сложность std::string.find() не определяется стандартом. Будем считать, что она Na * Nb в худшем случае, как при ней написано. Ваш алгоритм, без учёта сложности find(), в худшем случае отработает Na/Nb раз -- если Na будет полностью состоять из Nb. С учётом сложности find(), ваш алгоритм нахождения всех подстрок в строке сделает (Na / Nb) * Na * Nb операций, что есть Na ^ 2. Тут я, конечно, не учитываю, что обе эти ситуации худшего случая вместе скорее всего невозможны. 0

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	18.05.2022, 01:29	3
	Сообщение от lemegeton Я фиг знает, какую сложность мы считаем. ))) Когда-то давно, на форуме серьезных математиков, мне было достаточно забавно узнать, что при оценке "настоящей" сложности учитывается все, например операция сложения двух чисел имеет сложность не O(1) а O(log(n)), потому что именно столько бит требует их двоичное представление, и для больших чисел это важно А то там были любители предложить алгоритмы проверки чисел на простоту асимптотически лучше известных, но после подобных уточнений все сразу вставало на свои места А так, в рабоче-крестьянском смысле, все числа влезают в лонг лонг, складываются за O(1) и т.п. И жизнь вместе с оценкой такой "ненастоящей" сложности становится гораздо проще 2

@lemegeton 4773 / 2582 / 894 Регистрация: 29.11.2010 Сообщений: 5,590
	18.05.2022, 01:42	4
	"Серьезные математики" это такие дядьки, от которых хер чего добьешься, пока вопрос не будет сформулирован так, что ответ на него уже содержится в самом вопросе? ))) 1

@_Ivana 4817 / 2278 / 287 Регистрация: 01.03.2013 Сообщений: 5,947 Записей в блоге: 28
	18.05.2022, 01:47	5
	Именно так! Тем более, что на том форуме было строго контролируемое модераторами правило - бан падавану за отсутствие собственных попыток решения и бан отвечающим за решение "простых учебных задач" (в число коих входили, как вы понимаете, и не очень простые, в общепринятом смысле). Кстати, на этом благословенном форуме как минимум первая часть этих требований также отражена в правилах, но если бы они реально исполнялись, то вой разнесся бы по всему халяво-рунету, и местные админы потеряли бы траффик и доходы от рекламы, поэтому маемо шчо маемо (С) 1

@lemegeton 4773 / 2582 / 894 Регистрация: 29.11.2010 Сообщений: 5,590
	18.05.2022, 15:23	6
	Сообщение от _Ivana не очень простые, в общепринятом смысле Представляю, какие стандарты тривиальности имеют модераторы на форуме серьезных математиков. Мат аппарат большинства программистов весьма скуден, особенно относительно "серьезных математиков". Я тут час писал программку, считающую обратную матрицу. А там всего-то пяток понятий. А уж если надо тригонометрию порешать -- вэлкам ту гуголь. Яб там с первого вопроса в баню ушёл. Добавлено через 3 минуты Сообщение от _Ivana на этом благословенном форуме как минимум первая часть этих требований также отражена в правилах, но если бы они реально исполнялись, то вой разнесся бы по всему халяво-рунету, и местные админы потеряли бы траффик и доходы от рекламы, поэтому маемо шчо маемо (С) Капитализм он такой. Хотя я лично не возражаю. Меня это развлекает и ЧСВ почесать приятно. Ну и потом, если бы я не решал эти студ задачки, уже сто раз бы забыл даже простейшую математику. ))) Да будет хватать местным админам на бутерброд с красной икрой во веки вечные. 0

@Kuzia domovenok 4064 / 3318 / 924 Регистрация: 25.03.2012 Сообщений: 12,493 Записей в блоге: 1
	18.05.2022, 16:02	7
	_Ivana, каким макаром n означающее параметр алгоритма (мы же в каком-то алгоритме сложность оцениваем, например n - длина строки в этом посте) вдруг стало обозначать разрядность складываемых чисел? Вы же ссылаетесь на учёт алгоритмической сложности сложения в работе алгоритма поиска строк? Типичное сложение тёплого с мягким. Если что у нас и складывается в программе, то явно в неизменных типах чисел и с неизменной сложностью процесса сложения, какие бы строки на входе не были! 0