Сортировка данных (c#)sorting data (c#)

Оценка алгоритма сортировки

Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти:

  • Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = |A|. Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n2). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей всегда нуждаются по меньшей мере в сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью O(n log log n log log log n), использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О-обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за O(log2n) операций. При этом число n должно быть заранее известно;
  • Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют O(log n) памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет O(1)). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте.

Оптимальность O(nlog⁡(n)){\displaystyle O(n\log(n))}

Задача сортировки в общем случае предполагает, что единственной обязательно наличествующей операцией для элементов является сравнение. Это делает невозможным реализацию алгоритма Хана, использующего арифметические действия. Рассмотрим схему алгоритма, когда единственным возможным действием над элементами является их сравнение.

Пусть по ходу работы алгоритмом производится k{\displaystyle k} сравнений. Ответом на сравнение двух элементов a{\displaystyle a} и b{\displaystyle b} может быть один из двух вариантов (a<b{\displaystyle a<b} или a>b{\displaystyle a>b}). Значит, всего возможно 2k{\displaystyle 2^{k}} вариантов комбинаций ответов на k{\displaystyle k} вопросов.

Количество перестановок из n{\displaystyle n} элементов равно n!{\displaystyle n!}. Для того, чтобы можно было провести из множества ответов на сравнения на множество перестановок, количество сравнений должно быть не меньше, чем log2⁡n!{\displaystyle \log _{2}{n!}} (это обеспечивается тем, что сравнение — единственная разрешённая операция).

Прологарифмировав формулу Стирлинга, можно обнаружить, что log2⁡n!=log2⁡(2πn(ne)n)=log2⁡2πn+nlog2⁡n−nlog2⁡e∼nlog2⁡n=O(nlog⁡n){\displaystyle \log _{2}{n!}=\log _{2}{\left({\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\right)}=\log _{2}{\sqrt {2\pi n}}+n\log _{2}{n}-n\log _{2}{e}\sim n\log _{2}{n}=O(n\log {n})}

Не спеша, эффективно и правильно – путь разработки. Часть 3. Практика

Черновой вариант книги Никиты Зайцева, a.k.a.WildHare. Разработкой на платформе 1С автор занимается с 1996-го года, специализация — большие и по-хорошему страшные системы. Квалификация “Эксперт”, несколько успешных проектов класса “сверхтяжелая”. Успешные проекты ЦКТП. Четыре года работал в самой “1С”, из них два с половиной архитектором и ведущим разработчиком облачной Технологии 1cFresh. Ну — и так далее. Не хвастовства ради, а понимания для. Текст написан не фантазером-теоретиком, а экспертом, у которого за плечами почти двадцать три года инженерной практики на больших проектах.

Порядок команды ORDER BY в запросе

Сортировка строк чаще всего проводится вместе с условием на выборку данных. Команда ORDER BY ставится после условия выборки WHERE. Например, выбираем товары с ценой меньше 100 рублей, упорядочив по названию в алфавитном порядке:

SELECT * FROM goods WHERE price 100 ORDER BY price ASC

Цели урока:

Образовательные:

формировать понятие «сортировка информации»; рассмотреть виды сортировок; познакомить с алгоритмом простой и вложенной сортировок; научить сортировать данные в Microsoft Access; формировать умение работать с конструктором запросов; развивать навыки по заполнению и редактированию базы данных.

Развивающие: развивать алгоритмическое и логическое мышление; развивать умение работать в группе; развивать умение анализировать результаты своей работы.
Воспитательные: Воспитывать чувства коллективизма, ответственности, аккуратности.

Оборудование и материалы:

  • мультимедийная презентация , экран, проектор;
  • компьютеры с установленной СУБД Microsoft Access;
  • заранее заготовленная и записанная на всех компьютерах база данных «Небоскрёбы» ;
  • дидактический материал с алгоритмом выполнения практической работы ;
  • дидактический материал с алгоритмами различных способов расширения базы данных .

Структура урока:

  1. Организационный момент — 1 мин.
  2. Актуализация знаний учащихся — 10 мин.
  3. Изучение нового материала — 15 мин.
  4. Практическая работа на закрепление нового материала — 15 мин.
  5. Домашнее задание — 1 мин.
  6. Оценка работы и подведение итогов — 3 мин.

1. Организационный момент.

Приветственное слово учителя. Проверка присутствующих.

2. Актуализация знаний учащихся.

Ребята, чтобы узнать тему нашего сегодняшнего урока, вам предстоит разгадать «Чайнворд».

Вопросы к «Чайнворду»:

  1. Один из видов моделей данных, в котором принята свободная связь между элементами разных уровней.
  2. Столбец табличной базы данных.
  3. Объект СУБД Access, предназначенный для поиска и отбора данных по заданному условию.
  4. Тип данных, который заполняется компьютером автоматически с вводом каждой новой записи.
  5. Основной объект СУБД Access, предназначенный для хранения данных.
  6. Объект СУБД Access, выводящий данные из таблиц в удобном для чтения виде.
  7. Один из видов моделей данных, в котором информация хранится в виде таблиц.
  8. Уникальное поле, записи которого не повторяются.
  9. Один из режимов работы с объектами СУБД Access (Режим, в котором создаётся структура таблицы).
  10. Строка табличной базы данных.

Ответы: 1 — сетевая, 2 — поле, 3 — запрос, 4 — счётчик, 5 — таблица, 6 — форма, 7 — реляционная, 8 — ключевое, 9 — конструктор, 10 — запись.

Ключевое слово — сортировка.

3. Изучение нового материала.

Итак, тема сегодняшнего урока «Сортировка информации в БД». Записываем в тетрадь. .

Эпиграфом к уроку являются слова Александра Анатольевича Стекольникова:

Выдержки из книги Чистый код

Недавно я прочитал книгу «Чистый код» Роберта Мартина (Robert Cecil Martin). В ней описываются принципы организации и форматирование исходного кода программы так, чтобы в дальнейшем было легко поддерживать такой код.
Эта книга является библией для многих программистов, но вот в среде программистов 1С, к сожалению, не очень распространено чтение подобной фундаментальной литературы.
Книга более 400 страниц и так много порой лениво читать, да и времени всегда не хватает. По этому я решил выделить в виде цитирования по разделам самые важные моменты. А также снабдил текст своими примерами кода.

Формулировка задачи

Пусть требуется упорядочить N элементов: R1,R2,…,Rn{\displaystyle R_{1},R_{2},\dots ,R_{n}}. Каждый элемент представляет из себя запись Rj{\displaystyle R_{j}}, содержащую некоторую информацию и ключ Kj{\displaystyle K_{j}}, управляющий процессом сортировки. На множестве ключей определено отношение порядка «<» так, чтобы для любых трёх значений ключей a,b,c{\displaystyle a,b,c} выполнялись следующие условия:

  • : либо a<b{\displaystyle a<b}, либо a>b{\displaystyle a>b}, либо a=b{\displaystyle a=b};
  • закон транзитивности: если a<b{\displaystyle a<b} и b<c{\displaystyle b<c}, то a<c{\displaystyle a<c}.

Данные условия определяют математическое понятие линейного или совершенного упорядочения, а удовлетворяющие им множества поддаются сортировке большинством методов.

Задачей сортировки является нахождение такой перестановки записей p(1)p(2)…p(n){\displaystyle p(1)p(2)\dots p(n)} с индексами {1,2,…,N}{\displaystyle \{1,2,\dots ,N\}}, после которой ключи расположились бы в порядке неубывания:

Kp(1)⩽Kp(2)⩽⋯⩽Kp(n){\displaystyle K_{p(1)}\leqslant K_{p(2)}\leqslant \dots \leqslant K_{p(n)}}

Сортировка называется устойчивой, если не меняет взаимного расположения элементов с одинаковыми ключами:

p(i)<p(j){\displaystyle p(i)<p(j)} для любых Kp(i)=Kp(j){\displaystyle K_{p(i)}=K_{p(j)}} и i<j{\displaystyle i<j}.

Методы сортировки можно разделить на внутренние и внешние. Внутренняя сортировка используется для данных, помещающихся в оперативную память, за счёт чего является более гибкой в плане структур данных. Внешняя сортировка применяется, когда данные в оперативную память не помещаются, и ориентирована на достижение результата в условиях ограниченных ресурсов.

Сортировка по цвету ячейки и по шрифту

Программа Excel предоставляет пользователю богатые возможности форматирования. Следовательно, можно оперировать разными форматами.

Сделаем в учебной таблице столбец «Итог» и «зальем» ячейки со значениями разными оттенками. Выполним сортировку по цвету:

  1. Выделяем столбец – правая кнопка мыши – «Сортировка».
  2. Из предложенного списка выбираем «Сначала ячейки с выделенным цветом».
  3. Соглашаемся «автоматически расширить диапазон».

Сортировка данных (c#)sorting data (c#)

Программа отсортировала ячейки по акцентам. Пользователь может самостоятельно выбрать порядок сортировки цвета. Для этого в списке возможностей инструмента выбираем «Настраиваемую сортировку».

В открывшемся окне вводим необходимые параметры:

Сортировка данных (c#)sorting data (c#)

Здесь можно выбрать порядок представления разных по цвету ячеек.

По такому же принципу сортируются данные по шрифту.

Свойства и классификация

  • Устойчивость (англ. stability) — устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами.
  • Естественность поведения — эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше.
  • Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет O{\displaystyle O}(n⋅log⁡n{\displaystyle n\cdot \log n}), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы.

Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два:

  • Внутренняя сортировка

    В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки.

    оперирует массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте без дополнительных затрат.

  • Внешняя сортировка оперирует запоминающими устройствами большого объёма, но не с произвольным доступом, а последовательным (упорядочение файлов), то есть в данный момент «виден» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным во внешней памяти производится намного медленнее, чем операции с оперативной памятью.

    • Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим.
    • Объём данных не позволяет им разместиться в ОЗУ.

Также алгоритмы классифицируются по:

  • потребности в дополнительной памяти или её отсутствию
  • потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствию таковой

§ 5.2. Сортировка и поиск данных в электронных таблицах

Содержание урока

5.2. Сортировка и поиск данных в электронных таблицах

5.2. Сортировка и поиск данных в электронных таблицах

Сортировка данных в столбцах электронной таблицы. Электронные таблицы позволяют сортировать данные в отдельных столбцах. Если в столбец электронной таблицы ввести данные одного типа (числа, текст, даты или время), можно произвести их сортировку по возрастанию или убыванию. Ниже приведена табл.5.2, в которой сортировка данных в столбцах проведена следующим образом:в столбце А — сортировка чисел по убыванию; в столбце В — сортировка текста по убыванию; в столбце С — сортировка дат по возрастанию; в столбце D — сортировка времени по возрастанию.

Таблица 5.2. Сортировка чисел, текста, дат и времени в столбцах

Сортировка данных (c#)sorting data (c#)

При сортировке по возрастанию данные различных типов выстраиваются в следующем порядке:• числа — от наименьшего отрицательного до наибольшего положительного числа;
• текст — в алфавитном порядке (числа, знаки, латинский алфавит, русский алфавит);
• дата и время — в хронологическом порядке.

При сортировке по убыванию данные выстраиваются в порядке, обратном указанному выше.

Сортировка записей в электронных таблицах. Электронные таблицы могут содержать сотни и тысячи записей (строк). Часто бывает необходимо их упорядочить, т. е. расположить в определенной последовательности. Упорядочение записей называется сортировкой.

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

Значения, содержащиеся в выбранном поле, располагаются в порядке возрастания или убывания их значений, который определяется типом поля. В процессе сортировки целостность записей сохраняется, т. е. строки таблицы перемещаются целиком.

Сортировка данных в электронных таблицах — это упорядочение записей (строк) по значениям одного из полей.

Например, после сортировки по возрастанию по текстовому полю Фамилия база данных «Записная книжка» примет следующий вид (табл. 5.3).

Таблица 5.3. Результат сортировки базы данных «Записная книжка»

Сортировка данных (c#)sorting data (c#)

В электронных таблицах можно проводить вложенную сортировку, т. е. сортировать данные последовательно по нескольким полям. При вложенной сортировке строки, имеющие одинаковые значения в ячейках первого поля, будут упорядочены по значениям в ячейках второго поля, а строки, имеющие одинаковые значения во втором поле, будут упорядочены по значениям третьего поля.

Поиск данных в электронных таблицах. Поиск данных в электронных таблицах осуществляется с помощью фильтров. Фильтр просто скрывает в исходной таблице записи, не удовлетворяющие условиям поиска.

Поиск данных в электронной таблице — это отбор записей (строк), удовлетворяющих условиям поиска, заданным в форме фильтра.

Условия поиска записей создаются с использованием операторов сравнения (=, >, < и т. д.).

Для числовых данных существуют следующие операции сравнения:= (равно);
> (больше);
< (меньше);
>= (больше или равно);
<= (меньше или равно);
<> (не равно).

Для текстовых данных возможны следующие операции сравнения:• равно (сравниваются все символы);
• начинается с и не начинается с (сравниваются первые символы);
• заканчивается на и не заканчивается на (сравниваются последние символы);
• содержит и не содержит (сравниваются последовательности символов в различных частях текста).

В электронной таблице для задания условия поиска необходимо в базе данных выделить поле, выбрать операцию сравнения и ввести число или последовательность символов. В процессе поиска данные, хранящиеся в ячейках таблицы, будут сравниваться с введенными данными.

В результате будут отобраны только те записи базы данных, которые содержат данные, удовлетворяющие условию поиска.

Простые фильтры содержат условие поиска записей только для одного поля. Составные фильтры содержат несколько условий поиска для различных полей. В результате применения составного фильтра будут отобраны только те записи, которые удовлетворяют всем условиям одновременно.

Например, если в базе данных «Записная книжка» ввести простой фильтр для поля Фамилия, состоящий из условия равно Иванов, то будет найдена и оставлена на экране одна запись базы данных (табл. 5.4).

Таблица 5.4. Результат применения фильтра для базы данных «Записная книжка»

Сортировка данных (c#)sorting data (c#)

Контрольные вопросы

1. В чем состоит различие между сортировкой данных в базе данных и сортировкой данных в столбцах электронной таблицы?

2. В чем состоит различие между простыми и составными фильтрами?

Cкачать материалы урока

Сравнительный анализ времени работы алгоритмов

• Алгоритмы сортировки, описанные в текущей главе, используют разные методы и обладают различными характеристиками. Сведены в таблицу:

Сортировка Время работы Метод Область использования
Вставкой O(n2) Вставка Очень малые массивы
Выбором O(n2) Выбор Очень малые массивы
Пузырьковая O(n2) Двусторонние прохождения, ограничения рассматриваемых пределов Очень малые и частично сортированные массивы
Пирамидальная O(n·log n) Кучи, хранение полных деревьев в массиве Крупные массивы с неизвестным распределением
Быстрая O(n·log n)O(n2)-худший «Разделяй и властвуй», перемещение элементов в позицию, рандомизация во избежание худшего случая Крупные массивы без большого количества дубликатов, параллельная сортировка
Слиянием O(n·log n) «Разделяй и властвуй», объединение, внешняя сортировка Крупные массивы с неиз- вестным распределением, большие объемы данных, параллельная сортировка
Подсчетом O(n + m) Счет Крупные массивы с достаточно единообразным распределением значений

Создание пользовательской сортировки в Excel

В примере ниже мы хотим отсортировать данные на листе по размеру футболок (столбец D). Обычная сортировка расставит размеры в алфавитном порядке, что будет не совсем правильно. Давайте создадим настраиваемый список для сортировки размеров от меньшего к большему.

  1. Выделите любую ячейку в таблице Excel, которому необходимо сортировать. В данном примере мы выделим ячейку D2.
  2. Откройте вкладку Данные, затем нажмите команду Сортировка.
  3. Откроется диалоговое окно Сортировка. Выберите столбец, по которому Вы хотите сортировать таблицу. В данном случае мы выберем сортировку по размеру футболок. Затем в поле Порядок выберите пункт Настраиваемый список.
  4. Появится диалоговое окно Списки. Выберите НОВЫЙ СПИСОК в разделе Списки.
  5. Введите размеры футболок в поле Элементы списка в требуемом порядке. В нашем примере мы хотим отсортировать размеры от меньшего к большему, поэтому введем по очереди: Small, Medium, Large и X-Large, нажимая клавишу Enter после каждого элемента.
  6. Щелкните Добавить, чтобы сохранить новый порядок сортировки. Список будет добавлен в раздел Списки. Убедитесь, что выбран именно он, и нажмите OK.
  7. Диалоговое окно Списки закроется. Нажмите OK в диалоговом окне Сортировка для того, чтобы выполнить пользовательскую сортировку.
  8. Таблица Excel будет отсортирована в требуемом порядке, в нашем случае – по размеру футболок от меньшего к большему.

Сортировка в Excel по формату ячейки

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

  1. Выделите любую ячейку в таблице Excel, которому необходимо сортировать. В данном примере мы выделим ячейку E2.
  2. Откройте вкладку Данные, затем нажмите команду Сортировка.
  3. Откроется диалоговое окно Сортировка. Выберите столбец, по которому Вы хотите сортировать таблицу. Затем в поле Сортировка укажите тип сортировки: Цвет ячейки, Цвет шрифта или Значок ячейки. В нашем примере мы отсортируем таблицу по столбцу Способ оплаты (столбец Е) и по цвету ячейки.
  4. В поле Порядок выберите цвет для сортировки. В нашем случае мы выберем светло-красный цвет.
  5. Нажмите OK. Таблица теперь отсортирована по цвету, а ячейки светло-красного цвета располагаются наверху. Такой порядок позволяет нам четко видеть неоплаченные заказы.

Классификация сортировок[править]

Время работыправить

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

Лучшее время — минимальное время работы алгоритма на каком-либо наборе, обычно этим набором является тривиальный $\big $. Худшее время — наибольшее время.
У большинства алгоритмов временные оценки бывают $O(n \log n)$ и $O(n^2)$.

Памятьправить

Параметр сортировки, показывающий, сколько дополнительной памяти требуется алгоритму. Сюда входят и дополнительный массив, и переменные, и затраты на стек вызовов. Обычно затраты бывают $O(1)$, $O(\log n)$, $O(n)$.

Устойчивостьправить

Устойчивой сортировкой называется сортировка, не меняющая порядка объектов с одинаковыми ключами. Ключ — поле элемента, по которому мы производим сортировку.

Количество обменовправить

Количество обменов может быть важным параметром в случае, если объекты имеют большой размер. В таком случае при большом количестве обменов время алгоритма заметно увеличивается.

Детерминированностьправить

Алгоритм сортировки называется детерминированным, если каждая операция присваивания, обмена и т.д. не зависит от предыдущих.
Все сортирующие сети являются детерминированными.

Сортировка строк

Одним из наиболее частых приложений алгоритмов сортировки является сортировка строк. Обычно она производится так: сначала множество строк сортируется по первому символу каждой строки, затем каждое подмножество строк, имеющих одинаковый первый символ, сортируется по второму символу, и так до тех пор, пока все строки не будут упорядочены. При этом отсутствующий символ (при сравнении строки длины N со строкой длины N+1) считается меньше любого символа.

Применение данного метода к строкам, представляющим собой числа в естественной записи, выдаёт контринтуитивные результаты: например, «9» оказывается больше, чем «11», так как первый символ первой строки имеет бо́льшее значение, чем первый символ второй. Для исправления этой проблемы алгоритм сортировки может преобразовывать сортируемые строки в числа и сортировать их как числа. Такой алгоритм называется «числовой сортировкой», а описанный ранее — «строковой сортировкой».

Анализ сложности алгоритмов

• С увеличения размера входных данных обычно растет и сложность алгоритма, а следовательно, и время его выполнения. Сложность алгоритма принято называть порядком роста, который чаще всего представляется в виде нотации O-большое (от немецкого — порядок).

• Нотация О — большое – это всего лишь математический признак, который дает представление о ресурсах, потребляемых алгоритмом. Практически результаты могут быть разными. Но, как правило, это хорошая практика – пытаться снизить сложность алгоритмов.

1.1 Константный — O(1)

• Порядок роста O(1) означает, что вычислительная сложность алгоритма не зависит от размера входных данных. Следует помнить, однако, что единица в формуле не значит, что алгоритм выполняется за одну операцию или требует очень мало времени

Важно то, что это время не зависит от входных данных

1.2 Линейный — O(n)

• Порядок роста O(n) означает, что сложность алгоритма линейно растет с увеличением входного массива данных. Если алгоритм обрабатывает один элемент пять миллисекунд, то можно ожидать, что тысяча элементов обрабатываются за пять секунд. Такие алгоритмы легко узнать по наличию цикла по каждому элементу входного массива.

• Фрагмент алгоритма вычисления сложности О(n) на алгоритмическом языке С++

1.3 Логарифмический – O( log n)

• Порядок роста O( log n) означает, что время выполнения алгоритма растет логарифмически с увеличением размера входного массива данных, при этом в анализе алгоритмов по умолчанию используется логарифм по основанию 2. Большинство алгоритмов, работающих по принципу «деления пополам», имеют логарифмическую сложность. Например, метод Contains — бинарного дерева поиска (binary search tree) также имеет порядок роста O(log n).

1.4 Линеарифметический — O(n · log n))

• Линеарифметический (или линейно-логарифмический) алгоритм имеет порядок роста O(n ∙ log n). Некоторые алгоритмы, типа «разделяй и властвуй», например, сортировка слиянием и быстрая сортировка, попадают в эту категорию.

1.5 Квадратичный — O(n2)

• Время работы алгоритма с порядком роста O(n2) зависит от квадрата размера входного массива. Несмотря на то, что такой ситуации иногда не избежать, квадратичная сложность — повод пересмотреть используемые алгоритмы или структуры данных.

• Например, если массив из тысячи элементов потребует 1 000 000 операций, массив из миллиона элементов потребует 1 000 000 000 000 операций. Если одна операция требует миллисекунду для выполнения, то квадратичный алгоритм будет обрабатывать миллион элементов 32 года.

• Таким образом, при измерении сложности алгоритмов учитываются: количество операций, требуемых для завершения работы — вычислительная сложность, и объем ресурсов, в частности, памяти, который необходим алгоритму — пространственная сложность.

• Алгоритм, который выполняется в десять раз быстрее, но использует в десять раз больше памяти, может вполне подходить для серверной машины с большим объемом памяти. Но на встроенных системах, где количество памяти ограничено, такой алгоритм использовать нельзя .