Пошук, сортування та поняття складності у програмуванні, Детальна інформація

writeln(a[c[k]].x, ' ', a[c[k]].y);

end;

BEGIN

init; run; done

END.

Проаналізуємо складність наведеного алгоритму. Для сортування масиву потрібно O(nlogn) операцій. В процесі побудови оболонки кожна точка додається до послідовностей та вилучається з них не більше, ніж по одному разу. Тому складність власне побудови оболонки лінійна, і весь алгоритм має складність O(nlogn).

Задачі

15. Написати підпрограму підрахунку кількості різних значень елементів числового масиву. Складність підпрограми повинна бути O(nlogn), де n – кількість елементів масиву.

16. Написати підпрограму складності O(nlogn), що задає обчислення

а)перетину; б) симетричної різниці

двох n-елементних числових множин, поданих масивами.

17. Обчислити кількість трикутників, які можна скласти з N відрізків попарно різних додатних довжин, N < 2000. Складність програми не повинна перевищувати O(N2).

18. За N-елементним масивом A та перестановкою p(1), p(2), … , p(N) чисел 1, 2, … , N побудувати масив A[p(1)], A[p(2)], … , A[p(N)]. Допоміжний масив не використовувати.

19. Розглянемо прямокутний масив. Розташуємо елементи кожного рядка за зростанням. Потім розташуємо за зростанням елементи кожного стовпця. Довести, що кожний рядок залишиться впорядкованим.

20. (Задача про два станки) Є n деталей, кожна з яких проходить обробку спочатку на першому станку, потім на другому. Кожний станок здатний обробляти одночасно одну деталь і готовий до обробки наступної деталі одразу після обробки попередньої. Відомий час обробки кожної деталі на кожному із станків. Упорядкувати деталі таким чином, щоб час від початку обробки першої деталі до закінчення обробки останьої був якнайменшим. Наприклад, якщо перша деталь обробляється на станках 20 і 10 одиниць часу, а друга – 10 і 20, то за порядку деталей (перша, друга) одержимо час 50, а за порядку (друга, перша) – 40.