Когда дело доходит до оценки эффективности алгоритмов, решающую роль играют временная сложность и нотация Big-O. Они обеспечивают стандартизированный способ описания поведения алгоритмов во время выполнения и оценки их масштабируемости на основе размера входных данных. Давайте рассмотрим различные примеры, связанные с вычислением квадрата числа и их соответствующей временной сложностью.
Что такое нотация большого O?
По своей сути, нотация Big O описывает верхнюю границу или наихудший сценарий временной сложности алгоритма. Это позволяет нам понять, как производительность алгоритма масштабируется с большими входными данными. Обозначение Big O представлено как O (f (n)), где «f (n)» представляет функцию, которая аппроксимирует временную сложность алгоритма.
Чтобы упростить задачу, нотация Big O упрощает анализ временной сложности, сосредотачиваясь на наиболее важных факторах, влияющих на производительность алгоритма. Он игнорирует константы, члены более низкого порядка и коэффициенты, что дает нам общее представление о масштабируемости алгоритма.
Общие временные сложности Big O: Давайте рассмотрим несколько часто встречающихся временных сложностей Big O:
O(1) — постоянное время. Алгоритм занимает постоянное количество времени, независимо от размера входных данных. Например, доступ к элементу массива по индексу.
O(logN) — логарифмическое время. Время выполнения алгоритма увеличивается логарифмически с размером входных данных. Двоичный поиск — классический пример алгоритма с логарифмической временной сложностью.
O(n) — линейное время. Время выполнения алгоритма растет линейно с размером входных данных. Например, перебор каждого элемента в массиве.
O(n²) — квадратичное время. Время выполнения алгоритма экспоненциально растет с увеличением размера входных данных. Общие примеры включают вложенные циклы, повторяющиеся по одному и тому же массиву.
O(1) Решение: прямое вычисление
Вычисление квадрата числа — простая задача, которую можно выполнить за постоянное время. Умножая число само на себя, мы получаем квадрат. Вот пример:
int square(int n) { return n * n; // take constant time c1 }
Временная сложность этого решения равна O(1), потому что вычисление требует постоянного количества операций, независимо от значения n
. Он обеспечивает превосходную эффективность при увеличении размера входных данных.
O(n) Решение: итеративный расчет
Хотя вычисление квадрата числа может быть выполнено за постоянное время, мы можем разработать пример, демонстрирующий временную сложность O(n):
int square(int n) { int result = 0; // c1 for (int i = 0; i < n; ++i) { // n*c2 result += n; // n*c3 } return result; // c4 }
В этой нетрадиционной реализации мы моделируем возведение в квадрат числа n
, выполняя итеративное сложение n
раз. Поскольку цикл повторяется n
раз, временная сложность становится O(n). Хотя этот пример неэффективен по сравнению с прямым вычислением, он демонстрирует алгоритм с линейной временной сложностью.
Общее затраченное время можно выразить как сумму c2n + c3n + c1 + c4. Если мы рассмотрим c2n + c3n как c0n и c1 + c4 как c, общее время можно упростить до c0n + c, что представляет сложность O(n).
O(n²) Решение: вычисление вложенного цикла
Другой пример, демонстрирующий более высокую временную сложность, а именно O(n²), выглядит следующим образом:
int square(int n) { int result = 0; // c1 for (int i = 0; i < n; ++i) { // n*c2 for (int j = 0; j < n; ++j) { // n*c3 result += 1; // n*n*c4 } } return result; // c5 }
Вот разбивка анализа временной сложности:
- Инициализация
result
занимает постоянное время: O(1) или c1. - Внешний цикл повторяется
n
раз: O(n) или n * c2. - Для каждой итерации внешнего цикла внутренний цикл также повторяется
n
раз: O(n) или n * c3. - В каждой итерации обоих циклов выполняется оператор
result += 1
: O(1) или c4. - Поскольку вложенные циклы повторяются
n * n
раз, временная сложность оператораresult += 1
становится O(n^2) или n * n * c4. - Наконец, оператор return занимает постоянное время: O(1) или c5.
Чтобы рассчитать общую временную сложность, мы суммируем сложности каждого шага: общее затраченное время можно выразить как сумму c1 + n * c2 + n * c3 + n * n * c4 + c5. Если мы рассмотрим c6 = c4, c7 = c2 + c3 и c8 = c1 + c5, общее время можно упростить до c6n² + c7n + c8, что представляет собой O(n²), поскольку доминирующий член равен c6 * n². Вложенные циклы вносят свой вклад в квадратичную временную сложность, что указывает на то, что время выполнения увеличивается квадратично с размером входных данных n
.
O(logN) Решение: двоичный поиск
Двоичный поиск — это эффективный алгоритм поиска элементов в отсортированной коллекции. Он работает путем многократного деления диапазона поиска пополам, что приводит к временной сложности O (logN). Давайте рассмотрим пример бинарного поиска, реализованного на C++:
int binarySearch(const std::vector<int>& arr, int target) { int left = 0; // c1 int right = arr.size() - 1; // c2 while (left <= right) { // O(logN) int mid = left + (right - left) / 2; // c3 std::cout << "target : " << target << ", mid : " << mid << ", left : " << left << ", right : " << right << std::endl; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; // c4 } else { right = mid - 1; // c5 } } return -1; // c6 }
В этой реализации мы определяем функцию binarySearch
, которая принимает отсортированный вектор arr
и целевое значение target
в качестве входных данных. Функция инициализирует левый и правый индексы, чтобы отметить границы диапазона поиска.
Внутри цикла while
мы вычисляем средний индекс mid
по формуле (left + right) / 2
. Мы сравниваем элемент со средним индексом arr[mid]
с целевым значением, чтобы определить, равны ли они, меньше или больше друг друга.
Если средний элемент равен целевому, мы возвращаем индекс mid
, указывающий на успешное совпадение. Если средний элемент меньше целевого, мы корректируем левый индекс до mid + 1
, эффективно сужая диапазон поиска до правой половины. Если средний элемент больше целевого, мы устанавливаем правый индекс на mid - 1
, сужая диапазон поиска до левой половины.
Цикл продолжается до тех пор, пока левый индекс не станет больше правого индекса, указывая на то, что цель не найдена в коллекции. В этом случае мы возвращаем -1, чтобы указать на неудачный поиск.
Временная сложность бинарного поиска составляет O(logN), потому что диапазон поиска делится пополам с каждой итерацией. В результате алгоритм может эффективно находить цель за логарифмическое время относительно размера входного массива (N).
Этот пример демонстрирует временную сложность O(logN) бинарного поиска и демонстрирует его эффективность при эффективном поиске элементов в отсортированной коллекции.
Учитывая индивидуальные временные сложности внутри цикла, у нас есть c3 * logN для вычисления среднего индекса и (c4 + c5) * logN для корректировки левого и правого индексов. Общая временная сложность может быть упрощена как c0 * logN + c, где c0 представляет собой объединенные коэффициенты c3, c4 и c5, а c представляет коэффициенты c1, c2 и c6.
Вот использование бинарного поиска в основной функции.
int main() { std::vector<int> arr; for ( int i=1;i<=1024;i++) { arr.push_back(i*2); } int target = 2; int index = binarySearch(arr, target); if (index != -1) { std::cout << "Target found at index: " << index << std::endl; } else { std::cout << "Target not found in the array." << std::endl; } return 0; } Output: target : 2, mid : 511, left : 0, right : 1023 target : 2, mid : 255, left : 0, right : 510 target : 2, mid : 127, left : 0, right : 254 target : 2, mid : 63, left : 0, right : 126 target : 2, mid : 31, left : 0, right : 62 target : 2, mid : 15, left : 0, right : 30 target : 2, mid : 7, left : 0, right : 14 target : 2, mid : 3, left : 0, right : 6 target : 2, mid : 1, left : 0, right : 2 target : 2, mid : 0, left : 0, right : 0
В этой функции main
создается вектор arr
, который заполняется четными числами в диапазоне от 2 до 2048 (включительно) с использованием цикла. Вектор будет содержать 1024 элемента.
Целевое значение установлено равным 2, которое присутствует в векторе. Затем вызывается функция binarySearch
с вектором arr
и целевым значением.
Если цель найдена (индекс не равен -1), печатается сообщение о том, что цель найдена, вместе с соответствующим индексом. В противном случае выводится сообщение о том, что цель не найдена в массиве.
Когда этот код выполняется, алгоритм бинарного поиска эффективно находит целевой элемент в отсортированном векторе.
Когда целевое значение изменено на 128, результат выполнения функции main
будет следующим:
target : 128, mid : 511, left : 0, right : 1023 target : 128, mid : 255, left : 0, right : 510 target : 128, mid : 127, left : 0, right : 254 target : 128, mid : 63, left : 0, right : 126 Target found at index: 63
Когда целевое значение установлено на 3, алгоритм бинарного поиска не найдет его, поскольку целевое значение 3 отсутствует в отсортированном векторе. В этом наихудшем сценарии алгоритм по-прежнему будет работать эффективно с временной сложностью O(logN). Потребуется примерно 10 шагов (логарифмическая база 2 из 1024), чтобы определить, что целевое значение отсутствует в массиве.
Когда вы выполняете этот код, он демонстрирует наихудший сценарий бинарного поиска, демонстрируя его эффективность, даже если целевое значение не найдено в отсортированном массиве.
target : 3, mid : 511, left : 0, right : 1023 target : 3, mid : 255, left : 0, right : 510 target : 3, mid : 127, left : 0, right : 254 target : 3, mid : 63, left : 0, right : 126 target : 3, mid : 31, left : 0, right : 62 target : 3, mid : 15, left : 0, right : 30 target : 3, mid : 7, left : 0, right : 14 target : 3, mid : 3, left : 0, right : 6 target : 3, mid : 1, left : 0, right : 2 target : 3, mid : 0, left : 0, right : 0 Target not found in the array.
В заключение, нотация Big O обеспечивает стандартизированный способ измерения алгоритмической эффективности. Понимая эту нотацию, разработчики могут принимать более эффективные решения, что приводит к более эффективным и масштабируемым программным решениям.