Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Побудова опуклої оболонки. Методи
|
|
6. Найближча пара, метод «Розділяй та пануй»
Примітка1: часову оцінку складності сортування списку точок по координаті х віднесемо до попередньої обробки вхідної множини, в найгіршому випадку сортування буде потребувати O(
), а в кращому O(Nlog2N). Сортування множини точок по координаті у можно виконувати за O(
) прямо під час кроку злиття двох вже відсортованих по у множин.
Примітка2: на етапі злиття, маючи відсортовані по y точки, ми розглядаємо відстань тільки між тими точками, між якими різниця ординат менше нашої мінімальної дистанції (а не відстань між всіма точками першої і другої множин).
Примітка3 (для тих, кто сумнівається, що крок 6 виконується за лінійний час):
Примітка4 (сама очевидність): щоб показати, що часова оцінка складності дійсно дорівнює O(Nlog2N) треба показати, що часова оцінка на кроці злиття дорівнює O(), а враховуючи Примітку2 і Примітку3 бачимо, що це так і є.
Date: 2015-09-24; view: 390; Нарушение авторских прав