Время выполнения длинного массива фиксированного размера

Question

Зависит ли время выполнения алгоритма от длины массива?Я понимаю, что если длина массива неизвестна, мы скажем, что время выполнения следующего алгоритма равно O (n).

   public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    System.out.print("Size of array: ");

    int lengthOfArray = sc.nextInt();
    int[] longArray = new int[lengthOfArray];

    for (int i = 0; i < longArray.length; i++) {
        System.out.println("Hello" + i);
    }

}

Однако, если длина массива известна и фиксирована.Будет ли оно считаться постоянным временем, т. Е. O (1), или все еще считается O (n).

   public static void main(String[] args) {

    int[] longArray = new int[99];

    for (int i = 0; i < longArray.length; i++) {
        System.out.println("Hello" + i);
    }

}

Answer 1

Сложность времени: O (n) означает, что время выполнения вашего метода определяется входом .

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

Хорошее объяснение из вики :

Говорят, что алгоритм занимает линейное время или время O (n), если его сложность по времени равна O (n). Неформально это означает, что время работы увеличивается максимально линейно с размером входа. Точнее, это означает, что существует постоянная c, такая, что время выполнения не более cn для каждого входа размера n. Например, процедура, которая суммирует все элементы списка, требует времени, пропорционального длине списка, если время добавления является постоянным или, по крайней мере, ограниченным константой.

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

Answer 2

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

Это O (n) для цикла, который не известен, потому что задача варьируется в зависимости от n (она может быть более сложной для миллионных записей и менее сложной для 5). Это все еще линейная сложность, хотя.

Если мы знаем длину n = 5, то она становится O (5), которая в основном равна 5 * O (1), а поскольку постоянные числа не учитываются, она становится сложностью O (1).

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