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