15. Оценки временной сложности алгоритма

Теория сложности вычислений возникла из потребности сравнивать быстродействие алгоритмов, чётко описывать их поведение (время исполнения и объём необходимой памяти) в зависимости от размера входа.

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

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

Примеры: O(n²) – сортировка пузырьком, O(n) – поиск наибольшего значения в массиве, и т.д.

16. Структура рекурсивных алгоритмов

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

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

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

17. Структура программы на языке C++

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

• Объявление и определение функции (функция main – главная). Функции — это блоки кода, выполняющие определенные операции. Если требуется, функция может определять входные параметры, позволяющие вызывающим объектам передавать ей аргументы. При необходимости функция также может возвращать значение как выходное.

• Директивы препроцессора. Директивы препроцессора, такие как #define и #ifdef, обычно используются для того, чтобы облегчить изменение исходного кода программ и их компиляцию в разных средах выполнения. Директивы в файле исходного кода позволяют препроцессору выполнять определенные действия.

• Операторы (такие как сложение, вычитание, доступ к элементу массива по индексу и т.д.)

18. Методы доступа к функциям из библиотек и пакетов

Нужно подключить заголовочный файл (#include <something>) и пространство имён (using namespace something).

19. Описания, выражения и операторы в языке C++

Описание - это оператор, вводящий имя в программе. Оно может также инициализировать объект с этим именем. Выполнение описания означает, что когда поток управления доходит до описания, вычисляется инициализирующее выражение (инициализатор) и производится инициализация. Например: int i = 1;

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

В большинстве программ на C++ широко применяются указатели. Унарная операция * разыменовывает указатель, т.е. *p есть объект, на который указывает p. Эта операция также называется косвенной адресацией. Например, если имеется char* p, то *p есть символ, на который указывает p. Часто при работе с указателями бывают полезны операция увеличения ++ и операция уменьшения --. Предположим, p указывает на элемент вектора v, тогда p++ делает p указывающим на следующий элемент.

В этом разделе описываются выражения С++. Выражения — это последовательности операторов и операндов, используемые в следующих целях:

• Вычисление значения из операндов.

• Назначение объектов или функций.

20. Арифметические типы данных в языке C++

Целый тип (int). Размер типа int не определяется стандартом, а зависит от компьютера и компилятора. Для 32-разрядного процессора под величины этого типа отводится 4 байта, для 64-разрядного – 8 байт.

Вещественный тип (float, double и long double). Стандарт C++ определяет три типа данных для хранения вещественных значений: float, double и long double. Вещественные типы данных хранятся в памяти компьютера иначе, чем целочисленные. Внутреннее представление вещественного числа состоит из двух частей – мантиссы и порядка. В IBM PC-совместимых компьютерах величины типа float занимают 4 байта, из которых один двоичный разряд отводится под знак мантиссы, 8 разрядов под порядок и 23 под мантиссу.

21. Символьные и логические данные в языке C++

Символьный тип (char) – обычно один байт, служит для представления символов в строке. Нуль-терминированный массив знаков – строка.

Логический тип (bool) – true/false.