1.4. Оцінки складності деяких задач

ФАКТИ:

1. Множина S скінчена (|S|=n). Щоб перевірити, чи , необхідно W(log₂n) часу.
2. (Задача сортування). Задана множина з S, необхідно її відсортувати: час W(nlog₂n).
3. Якщо деяка задача в d-вимірному просторі вимагає f(n) часу, то для розв'язання цієї задачі в просторі розмірності k>d також потрібно як мінімум f(n) часу.

1. Перевірка унікальності елементів: чи є на заданій множині два рівних елементи.
2. Перевірка рівності включення множин.
3. Перевірка перетину множин.
4. Перевірка на значимість. Задана множина S з n точок на площині: чи усі точки належать опуклій оболонці множини точок.
5. Перевірка e-близькості. Задана множина з n точок на площині S, чи є серед елементів цієї множини два елементи, які знаходяться на відстані e.
6. Об'єднання інтервалів.