Анализ на коректността на алгоритми.

Доказателства за коректност на рекурсивни алгоритми --
чрез индукция.  Алгоритъмът MAX BITONIC с доказателство
за коректност.

Доказателства за коректност на итеративни алгоритми --
чрез инварианти.  Какво е инвариант на цикъл в доказателство
за коректност на итеративен алгоритъм.
Алгоритъмът ALG 2SUM с доказателство за
коректност.
Алгоритъмът ALG MAX SUM PLUS DIST с доказателство за
коректност.

Анализ на сложността на алгоритми.
Големина на входа на алгоритъм.
Съществено еднакви входове на
сортиращ алгоритъм.

Сложност по време на алгоритъм -- в най-лошия
случай, в най-добрия случай и средна сложност
по време.

Асимптотични нотации.  Защо ползваме асимптотичните
нотации при описанието на сложността на алгоритми.

Асимптотична нотация Тита-голямо.

Последно модифициране: сряда, 26 февруари 2025, 17:37