Самостоятельная работа №1 По предмету: Алгоритмы проектирования Статические и динамические меры сложности алгоритма

МИНИСТЕРСТВО ПО РАЗВИТИЮ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И КОММУНИКАЦИЙ РЕСПУБЛИКИ УЗБЕКИСТАН
КАРШИНСКИЙ ФИЛИАЛ ТАШКЕНТСКОГО УНИВЕРСИТЕТА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ ИМЕНИ АЛЬ-ХОРАЗМИЙ
ФАКУЛЬТЕТ ТТ И ПО

САМОСТОЯТЕЛЬНАЯ РАБОТА №1
По предмету: Алгоритмы проектирования

1. 
   Статические и динамические меры сложности алгоритма.
   
2. 
   Оценка алгоритмов в худшем и среднем случаях.
   
3. 
   Плоские и логарифмические критерии сравнения для оценки временной и объемной сложности алгоритмов.
   

Подготовил: Нутфуллаев Шахзод
Студент 3-го курса гр. TT-13-20р


г. Карши 2023 год
Статические и динамические меры сложности алгоритма. Проблемы со временем и памятью.

ПЛАН:

1. 
   Статические и динамические меры сложности алгоритма. Проблемы со временем и памятью.
   
2. 
   Оценка алгоритмов в худшем и среднем случаях.
   
3. 
   Плоские и логарифмические критерии сравнения для оценки временной и объемной сложности алгоритмов.
   
4. 
   Краткое содержание
   
5. 
   Рекомендации
   

1. Оценка временной сложности алгоритма. Типы функций сложности алгоритма
Постоянное время
Алгоритм называется алгоритмом с постоянным временем (обозначается как время O (1)), если T(n) ограничено значением, которое не зависит от размера входных данных. Например, извлечение одного элемента в массиве занимает постоянное время, потому что для его поиска требуется одна инструкция. Однако поиск минимального значения в несортированном массиве не является операцией с постоянным временем, потому что нам нужно сканировать каждый элемент массива. эта операция занимает линейное время, O ( n ). Если количество элементов заранее известно и не меняется, такой алгоритм можно назвать алгоритмом с постоянным временем.
Несмотря на название «постоянное время», время выполнения не обязательно не зависит от размера задачи, но не должно быть верхнего предела времени выполнения.Например, задача «обменять значениями» а и б, при необходимости, в результате получаем a≤b", является задачей с постоянным временем, хотя время работы алгоритма может зависеть от существования неравенства a ≤ b или нет. Однако существует некоторая константа t, при которой время выполнения задачи не всегда увеличивается t.
Вот несколько примеров кода, которые выполняются непрерывно:
внутренний индекс = 5; целочисленный элемент = список; если (условие истинно), то в противном случае выполните некоторую операцию с постоянным временем выполнения для i = 1 для 100 для j = 1 для 200 выполните некоторую операцию с постоянным временем выполнения
Если T(n) равно O (некоторое постоянное значение), то T(n) равно O (1).