Заочная физико-техническая школа Московского физико-технического института         
Задачи и решения
  Вернуться к сообщениям форума  |  Ответить на сообщение 
Re: Информатика 10 класс задание №3 контрольный вопрос №4
Сообщение прислал(а): Олег (95-29-98-214.broadband.corbina.ru)
Дата написания: 11 февраля 2018г. 18:52:27
Общий подход.

Для данного алгоритма (например, метода пузырьковой сортировки) считаем, что на вход подаются N чисел.

Чтобы определить временную сложность в наихудшем случае, определяем этот наихудший случай, т.е. когда придется выполнять больше всего операций и вычисляем это количество как функцию от N.

Например, для пузырьковой сортировки наилучший случай (меньше всего операций, т.е. требуется один проход) - когда все уже отсортировано в нужном порядке (N-1 операций), а наихудший случай - это случай, когда входной массив представляет собой разные числа, отсортированные в обратном порядке. Общее количество операций в наихудшем случае пропорционально N*(N-1)/2, т.е. пропорционально N2 (т.е. N в квадрате).

Чтобы определить пространственную сложность в наихудшем случае, нужно определить этот наихудший случай, т.е. когда требуется больше всего памяти, и вычисляем этот объем памяти как функцию от N.

Например, в алгоритме пузырьковой сортировки во всех случаях используется одинаковый объем памяти, пропорциональный N (т.е. наихудший и наилучший случаи совпадают).

Сообщения в данном потоке
 Re: Информатика 10 класс задание №3 контрольный вопрос №4 (255) - Олег (95-29-98-214.broadband.corbina.ru) [11.02.18 18:52]

Ответить на сообщение
При публикации вопросов, связанных с задачами, приводите, пожалуйста, ИХ УСЛОВИЯ.
Тема сообщения:
Ваше имя:
Ваш E-Mail:
Текст сообщения:
[Добавить формулу]
Сотрудник ЗФТШ:   
  

© 2002-2018, ЗФТШ МФТИ
    Пожелания вебмастеру
ЛЕКТОРИЙ | ПРОГРАММЫ ОБУЧЕНИЯ | МЕТОДИСТЫ | ШКОЛЬНИКАМ
Разработка 100ляров