Когда дело доходит до оценки эффективности алгоритмов, решающую роль играют временная сложность и нотация 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 обеспечивает стандартизированный способ измерения алгоритмической эффективности. Понимая эту нотацию, разработчики могут принимать более эффективные решения, что приводит к более эффективным и масштабируемым программным решениям.