Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 19.01.2011, 15:14
Новичок

Отправить личное сообщение для carlos0n Посмотреть профиль Найти все сообщения от carlos0n
 
Регистрация: 19.01.2011
Сообщений: 6

подскажите время работы алгоритма
Здравствуйте. Есть задача:
Найти наибольший интервал не пересекающийся с другими интервалами.
Я отсортировал множество всех интервалов по началу (началу интервалов) пирамидальной сортировкой
Далее для начала проверим непресекающийся ли первый интервал.
если да, т.е. конец первого интервала меньше начала второго, то сохраним данные о нём в result.
иначе сохраним значение конца второго интервала к примеру в переменную z и будем делаее просмотриветь интервалы.
если мы найдём в промежутке от начала первого до z такой интервал, начало которого лежит в этом промежутке, а конец больше значения в z, то сохраним значение конца этого интервала в z. так будем идти до тех пор, пока не встретим интервал, начало которого не лежит в промежутке от начала первого до z. если найдем такой, то начнем проверять его на не пересекаемость, т.е. если начало текущего, больше конца предыдущего и конец текущего меньше начала последующего, и так же длинна текущего больше длинны предыдущего найденного не пересекающегося интервала, то интервал не пересекающийся и его данные надо сохранить.

правильно ли я понимаю, что время работы этого алгоритма O[n*log(n)] ?
пирамидальная сортировка работает O[n*log(n)] и нахождение наибольшего интервала в множестве занимает O(n) шагов?

Последний раз редактировалось carlos0n, 19.01.2011 в 15:40.
  #2  
Старый 19.01.2011, 15:18
Местный

Отправить личное сообщение для prografix Посмотреть профиль Найти все сообщения от prografix
 
Регистрация: 03.11.2006
Адрес: Москва
Сообщений: 167

Согласен.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Замер времени работы программы на C# гость Реализация, исходники, языки 6 06.05.2009 23:47
BuildHeap, линейное время гость Математические алгоритмы 6 21.03.2009 16:37
Сравнение времени работы leahov Сортировка и поиск 3 29.05.2008 10:42
алгоритм работы WinMerge и ему подобных гость Сортировка и поиск 1 27.12.2007 03:39
Подскажите название алгоритма и ссылку на него horry Математические алгоритмы 3 20.09.2007 12:25