Есть ли какие-либо изменения в сложности времени, если я смогу уменьшить количество циклов цикла вдвое?

Question

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

Сначала я подумал, что да, потому что при замене мест я должен проходить только половину символов в данной строке. Хотя, если подумать, это дало бы временную сложность O (.5n), которая была бы равна O (n), как при асимптотической сложности, мы игнорируем множители.

public static String reverse(String str) {

    char[] strArray = str.toCharArray();

    for (int i = 0; i < str.length()/2; i++) {

        char temp = strArray[str.length() - i - 1];
        strArray[str.length() - i - 1] = strArray[i];
        strArray[i] = temp;
    }

    return new String(strArray);
}

Возможно, я ответил на свой собственный вопрос, так как считаю, что это будет такая же сложность по времени, как если бы я перебрал все символы в строке, т. Е. O (n), но, возможно, я что-то пропустил и мне просто потребовались некоторые разъяснения.

Answer 1

Вы действительно ответили на свой вопрос.Сокращение времени вдвое для всех входных данных не меняет теоретической сложности времени.Теоретическая временная сложность просто измеряет, сколько времени для бега увеличивается по мере того, как ввод становится все больше и больше.И код, который у вас есть, все равно занимает вдвое больше времени, а вход вдвое длиннее (следовательно, это O(n)).