Нубский вопрос про std::vector
Стандарт требует кратное наращивание, чтобы получалось amortized constant time.
Реализации обычно используют что-то типа *1,5 или *2.
Реализации обычно используют что-то типа *1,5 или *2.
если добавляем в рамках текущего capacity, то O(1 если больше - у нас опаньки в виде O(n)Капитан что дальше подсказывает?
капитан подсказывает, что если у нас capactiy+=const, то
даже если мы имеем const раз O(1) и 1 раз O(n то в общем случае будет O(n).
если capacity*=2, то я что-то не соображу, как подсчитать..
какой правильный ответ?
"почти всегда O(1 но иногда, при неблагоприятных случаях имеем O(n)" ?
даже если мы имеем const раз O(1) и 1 раз O(n то в общем случае будет O(n).
если capacity*=2, то я что-то не соображу, как подсчитать..
какой правильный ответ?
"почти всегда O(1 но иногда, при неблагоприятных случаях имеем O(n)" ?
если capacity*=2, то я что-то не соображу, как подсчитать..При последовательном добавлении n элементов получим сумму:
O(1+2+4+...+2^t где 2^t - наибольшая степень двойки, не превосходящая n.
Эта сумма равна O(n значит, "среднее" время добавления одного элемента O(1).
Эта сумма равна O(n значит, "среднее" время добавления одного элемента O(1).какое среднее время, когда мы о О говорим? О обозначает худшее время, так что асимптотика будет О(m где m - уже имеющееся к этому моменту количество элементов.
Среднее с т.зрения асимптотики можно учесть оценив асимптотику добавления n элементов в список с m элементами. Там асимптотика будет O(n + n*log m + n) == O (n * log m + n). (Расширение будет происходить порядка логарифма раз в случае *х, т.к. будет на шагах № init capacity, init capacity * х, init capacity * х^2,... init capacity ^х^i <= m + n)
какое среднее время, когда мы о О говорим? О обозначает худшее время, так что асимптотика будет О(m где m - уже имеющееся к этому моменту количество элементов.O применимо к любым функциям, не только к максимуму-минимуму. Мсье не слышал о таком понятии, как математическое ожидание?
Среднее с т.зрения асимптотики можно учесть оценив асимптотику добавления n элементов в пустой список. Там асимптотика будет O(n + n*log n) == O (n * log n). (Расширение будет происходить порядка логарифма раз в случае *х, т.к. будет на шагах № init capacity, init capacity * х, init capacity * х^2,... init capacity ^х^i <= n)Бред. Расширение будет происходить порядка логарифма раз, но и размер там будет меньше n. Асимптотика добавления n элементов в пустой вектор равна O(n).
O применимо к любым функциям, не только к максимуму-минимуму. Мсье не слышал о таком понятии, как математическое ожидание?О работает в этом случае как максимум. Мсье предлагается ознакомиться с математическим определением.
в данном случае пусть g (n, m) - это функция сложности добавления элемента. Предположим, что f(n, m) = O(g(n, m. Тогда существует положительный c такой, что f(n, m) >= c * g(n, m); Если предположить, что f(n, m) = const, то очевидно, что можно подобрать достаточно большое m, чтобы это уравнение было неверным. Т.о. ассимптотика добавления 1 элемента в произвольный массив - это таки O(n хотя в большинстве случаев это случится за константное время
Бред. Расширение будет происходить порядка логарифма раз, но и размер там будет меньше n. Асимптотика добавления n элементов в пустой вектор равна O(n).Исправил на список с изначальной длиной m, чтобы было меньше вопросов.
Какая-то у тебя каша. Кидая ссылку на определение O ты тем не менее продолжаешь писать конструкции вида O(n * log m + n)
Тебе пишут, что подразумвают под амортизированным временем работы (а именно его пытаются оценить через O на что ты отвечаешь, не, вы не то смотрите, давайте лучше смотреть максимальное.
Тебе пишут, что подразумвают под амортизированным временем работы (а именно его пытаются оценить через O на что ты отвечаешь, не, вы не то смотрите, давайте лучше смотреть максимальное.
Асимптотика добавления n элементов в пустой вектор равна O(n).Поднимите руку те, кто считает, что увеличение емкости вектора происходит за константное время.
Амортизированное время константое.
Откуда это следует?
Можно провести амортизационный анализ. Опишу в общих чертах.
Пусть мы используем мультипликативную стратегию реаллокации с параметром m (при исчерпании текущего объема памяти![[math]$$V$$[/math]](mathimg.php?math=%24%24V%24%24)
выделяем новый объем ![[math]$$mV$$[/math]](mathimg.php?math=%24%24mV%24%24)
).
Пусть, для простоты, нам надо добавить![[math]$$N = m^k$$[/math]](mathimg.php?math=%24%24N%20%3D%20m%5Ek%24%24)
элементов в пустой вектор.
За время добавления мы проведем k реаллокаций, общая сложность которых![[math]$$O(S) = O(m^0 + m^1 + ... + m^k) = O\left(\frac{m^{k + 1} - 1}{m - 1}\right) = O\left(N \frac{m}{m - 1}\right)$$[/math]](mathimg.php?math=%24%24O%28S%29%20%3D%20O%28m%5E0%20%2B%20m%5E1%20%2B%20...%20%2B%20m%5Ek%29%20%3D%20O%5Cleft%28%5Cfrac%7Bm%5E%7Bk%20%2B%201%7D%20-%201%7D%7Bm%20-%201%7D%5Cright%29%20%3D%20O%5Cleft%28N%20%5Cfrac%7Bm%7D%7Bm%20-%201%7D%5Cright%29%24%24)
.
Поэтому амортизированная сложность одной операции равна![[math]$$O\left(\frac{m}{m - 1}\right) = O(1)$$[/math]](mathimg.php?math=%24%24O%5Cleft%28%5Cfrac%7Bm%7D%7Bm%20-%201%7D%5Cright%29%20%3D%20O%281%29%24%24)
.
Пусть мы используем мультипликативную стратегию реаллокации с параметром m (при исчерпании текущего объема памяти
Пусть, для простоты, нам надо добавить
За время добавления мы проведем k реаллокаций, общая сложность которых
Поэтому амортизированная сложность одной операции равна
В твоем анализе непонятен переход от Om^(k+1)-1)/(m-1 к O(Nm/(m-1.
Ну, я уже в принципе разобрался, там чуток похитрее механизм.
На странице 67 этой книги хорошо объяснено.
Ну, я уже в принципе разобрался, там чуток похитрее механизм.
На странице 67 этой книги хорошо объяснено.
> В твоем анализе непонятен переход от Om^(k+1)-1)/(m-1 к O(Nm/(m-1.
Из равенства N=m^k, не?
Из равенства N=m^k, не?
Тебе пишут, что подразумвают под амортизированным временем работы (а именно его пытаются оценить через O на что ты отвечаешь, не, вы не то смотрите, давайте лучше смотреть максимальное.Погуглил немного и понял, что вы хотите.
Похоже в интернете стало модно выражать амортизированное время через О большое, что является, мягко говоря, некорректным, т.к. см выше определение асимптотики. Среднее время кстати вроде считается как α(f(x (вроде).
Вобщем среднее время добавления - константа, время с начала пропорционально количеству, в уже заполненный - я вроде верно оценил.
Да, блин, что угодно можно выражать через O. Это всего-навсего предикат. При чем здесь асимптотика совершенно другой величины? Посчитал ты неверно. Там получится O(m+n).
А, да, тогда всё сходится 
Чото затупляю - грубо оценивал каждую реаллокацию в O(N).
Чото затупляю - грубо оценивал каждую реаллокацию в O(N).
Оставить комментарий
yolki
За сколько туда добавляется элемент через push_back ?не, я понимаю что там есть хранилище размера capacity, оно может увеличится, если место кончилось и т.п.
если добавляем в рамках текущего capacity, то O(1 если больше - у нас опаньки в виде O(n)
каким образом наращивается capacity ? (+const, *const) ?
как оценить общую сложность?