Вычисление временной и пространственной сложности Java-программы — важный шаг в анализе ее эффективности и производительности. Вот несколько общих шагов для расчета временной и пространственной сложности Java-программы.

Параллельное ядро

  • Определите алгоритм. Первым шагом является определение алгоритма, используемого в программе Java. Алгоритмы представляют собой пошаговые процедуры решения проблемы, а их временная и пространственная сложность зависит от конкретной реализации.
  • Подсчитайте операции. После определения алгоритма подсчитайте количество основных операций, выполняемых программой. Основные операции включают арифметические операции, сравнения и присваивания.
  • Определить наихудший сценарий. Чтобы определить временную сложность программы Java, необходимо определить наихудший сценарий для алгоритма. Это сценарий, в котором алгоритму требуется больше всего времени для выполнения.
  • Использовать нотацию Big O. Используйте нотацию Big O для выражения временной сложности программы Java. Обозначение Big O – это математическое обозначение, описывающее предельное поведение функции, когда аргумент стремится к определенному значению или бесконечности.
    Анализ пространственной сложности: чтобы проанализировать объемную сложность программы на Java, определите объем используемой памяти. программой в зависимости от размера ввода.
  • Использовать нотацию пространственной сложности. Подобно нотации временной сложности, используйте нотацию пространственной сложности (например, O(1), O(n), O(n^2) и т. д.) для выражения пространственной сложности Java-программа.

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

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

O(1) – постоянная временная сложность. Алгоритм имеет постоянную временную сложность, если для его выполнения требуется одинаковое количество времени независимо от размера входных данных. Например, доступ к элементу в массиве с использованием его индекса имеет постоянную временную сложность O (1).

public static void constantTime(int[] arr) {
    // Accessing the first element in the array takes the same amount of time
    // regardless of the input size
    System.out.println(arr[0]);
}

O(log n) — логарифмическая временная сложность. Алгоритм имеет логарифмическую временную сложность, если время его выполнения увеличивается логарифмически с увеличением размера входных данных. Например, алгоритм бинарного поиска имеет логарифмическую временную сложность O(log n).

public static int binarySearch(int[] arr, int key) {
    int low = 0;
    int high = arr.length - 1;
    
    while (low <= high) {
        int mid = (low + high) / 2;
        
        if (arr[mid] < key) {
            low = mid + 1;
        } else if (arr[mid] > key) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    
    return -1;
}

O(n) — линейная временная сложность. Алгоритм имеет линейную временную сложность, если время его выполнения увеличивается линейно с размером входных данных. Например, обход массива имеет линейную временную сложность O(n).

public static void linearTime(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        System.out.println(arr[i]);
    }
}

O(n log n) — линейная арифмическая временная сложность. Алгоритм имеет линейную временную сложность, если время его выполнения увеличивается как n, умноженное на логарифм n с размером входных данных. Например, алгоритм сортировки слиянием имеет линейно-временную сложность O(n log n).

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}
public static void merge(int[] arr, int left, int mid, int right) {
    int[] temp = new int[arr.length];
    int i = left;
    int j = mid + 1;
    int k = left;
    
    while (i <= mid && j <= right) {
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    
    while (j <= right) {
        temp[k++] = arr[j++];
    }
    
    for (i = left; i <= right; i++) {
        arr[i] = temp[i];
    }
}

O(n^2) – квадратичная временная сложность. Алгоритм имеет квадратичную временную сложность, если время его выполнения увеличивается пропорционально квадрату размера входных данных. Например, вложенный цикл, сравнивающий каждый элемент массива с каждым другим элементом того же массива, имеет квадратичную временную сложность O(n^2).

public static void quadraticTime(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            System.out.println(arr[i] + " " + arr[j]);
        }
    }
}

O(2^n) — экспоненциальная временная сложность. Алгоритм имеет экспоненциальную временную сложность, если время его выполнения удваивается с каждым увеличением размера входных данных. Например, метод грубой силы для решения задачи коммивояжера имеет экспоненциальную временную сложность O(2^n).

public static int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    
    return fibonacci(n - 1) + fibonacci(n - 2);
}

Это всего лишь несколько примеров многих возможных временных сложностей, с которыми можно столкнуться в алгоритмах.

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

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

Для последовательных операций сложность по времени суммируется. Например, если у нас есть программа с двумя последовательными операциями, одна со временной сложностью O(f(n)) и другая со временной сложностью O(g(n)), то составная временная сложность программы равна O(f (п) + г(п)).

Для вложенных операций временные сложности умножаются. Например, если у нас есть программа с внешним циклом с временной сложностью O(f(n)) и внутренним циклом с временной сложностью O(g(n)), то составная временная сложность программы равна O(f(n)). п) * г(п)).

Для ветвей мы берем максимальную временную сложность. Например, если у нас есть оператор if-else, в котором ветвь if имеет временную сложность O(f(n)) и ветвь else имеет временную сложность O(g(n)), то составная временная сложность оператора равна O (max(f(n), g(n))).
Рассмотрим пример программы с тремя функциями:

public static void main(String[] args) {
    int[] arr = {1, 2, 3, 4, 5};
    quadraticTime(arr);
    logarithmicTime(arr.length);
    linearithmicTime(arr);
}
public static void quadraticTime(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length; j++) {
            System.out.println(arr[i] + " " + arr[j]);
        }
    }
}
public static void logarithmicTime(int n) {
    int i = n;
    while (i > 1) {
        i /= 2;
    }
    System.out.println(i);
}
public static void linearithmicTime(int[] arr) {
    Arrays.sort(arr);
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum += arr[i];
    }
    System.out.println(sum);
}

Временная сложность каждой функции следующая:

quadraticTime: O(n^2)
логарифмическое время: O(log n)
linearithmicTime: O(n log n)
Составная временная сложность всей программы может быть рассчитана путем сложения временных сложностей трех функций, поскольку они выполняются последовательно:

O(n^2) + O(log n) + O(n log n) = O(n^2 + n log n)
Следовательно, составная временная сложность программы равна O(n^2 + n журнал n).

Спасибо. Для получения более подробной информации об эффективном программировании вы можете посетить мой сайт по адресу https://www.concurrentcore.com.