|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
05.03.2014, 20:01 | #1 |
Форумчанин
Регистрация: 11.02.2011
Сообщений: 131
|
Асимптотика итератора set
Собственно, вопрос: с какой асимптотикой работает ++I, где set<int>::iterator I;.
Я так понимаю, что в худшем случае нужно подняться на с самого нижнего уровня до верхнего - это даёт O(log(N)). Но при общем переборе всех вершин (именно это и требуется) от каждой вершины подъём будет ровно один раз и вход (снизу и сверху) не более трёх раз, что даёт в сумме O(N) (то есть O(1) на каждую вершину). Но не знаю, применена ли там какая-то оптимизация для итератора (может, список указателей упорядоченный). Верны ли мои предположения? Последний раз редактировалось БалаШагаЛ; 05.03.2014 в 21:49. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
deque. Ошибка при объявлении итератора | 8Observer8 | Общие вопросы C/C++ | 10 | 26.01.2013 00:31 |
Разыменовывание итератора | litviak | Общие вопросы C/C++ | 5 | 08.06.2012 14:29 |
использование итератора | Defunate | C# (си шарп) | 1 | 10.07.2011 15:55 |
Организация доступа к вектору посредством итератора | jennya | Visual C++ | 2 | 03.10.2010 15:14 |