Лучшее понимание сложности времени

Question

Я немного запутался (войдите в систему). Учитывая этот код

public static boolean IsPalindrome(String s) {
    char[] chars = s.toCharArray();
    for (int i = 0; i < (chars.length / 2); i++) {
        if (chars[i] != chars[(chars.length - i - 1)])
            return false;
        }
        return true;
    }
}

Я повторяюсь n / 2 раза. Таким образом, с увеличением длины n мое время увеличивается вдвое по сравнению с n. На мой взгляд, я подумал, что это именно то, что журнал? Но человек, который написал этот код, сказал, что это все еще O (N).

В каком случае цикла что-то может быть (log n)? Например этот код:

1. for (int i = 0; i < (n * .8); i++)

Это журнал? Я зацикливаю 80% длины n.

А как насчет этого?

2. for (int i = 1; i < n; i += (i * 1.2))

Это журнал? Если так, то почему.

Answer 1

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

Обозначение Big O используется для описания асимптотического поведения алгоритма как размера роста задачи (до бесконечности). Конкретные коэффициенты не имеют значения.

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

Итак, давайте вернемся к вашим примерам № 1 и № 2:

1. да, вы делаете только chars.length/2 итераций цикла, но если длина s удваивается, вы также удваиваете количество итераций. Это точно линейная сложность времени

2. аналогично предыдущему случаю вы делаете 0.8*n итераций, но если удвоить n, вы делаете вдвое больше итераций. Опять же, это линейно

Последний пример отличается. Коэффициент 1.2 не имеет большого значения. Важно то, что вы добавляете i к себе. Давайте перепишем это утверждение немного

i += (i * 1.2)

совпадает с

i = i + (i * 1.2)

что совпадает с

i = 2.2 * i

Теперь вы четко видите, что каждую итерацию вы более чем удваиваете i. Так что если вы удвоите n, вам понадобится только еще одна итерация (или даже та же самая). Это признак принципиально сублинейной временной сложности. И да, это пример O(log(n)), потому что для большого n вам нужно всего около log(n, base=2.2) итераций, и это правда, что

 log(n, base=a) = log(n, base=b) / log(n, base=b) = constant * log(x, base=b) 

, где constant равно 1/log(a, base=b)

Answer 2

1. for (int i = 0; i < (n * .8); i++) В первом случае вы можете заменить 0.8n другой переменной, назовем ее m.

for (int i = 0; i < m; i++) Вы повторяете м количество раз. Вы увеличиваете значение i одна единица в каждой итерации. Поскольку m и n являются просто именами переменных, сложность Big-O в вышеуказанном цикле составляет O (n).

2. for (int i = 0; i < n; i += (i * 1.2)) Во втором сценарии вы не увеличиваете значение i, значение i всегда будет 0. И это классический случай бесконечного цикла.

То, что вы ищете, это 2. for (int i = 1; i <= n; i += (i * 1.2)) Здесь вы увеличиваете значение i логарифмически (но не до основания 2).

Рассмотрим for (int i = 1; i <= n; i += i) Значение i удваивается после каждой итерации. значение i будет 1, 2, 4, 8, 16, 32, 64.. Скажем, значение n равно 64, ваш цикл завершится за 7 итераций, что составляет (log(64) to the base 2) + 1 (+1, потому что мы начинаем цикл с 1) числа операций. Следовательно, это становится логарифмической операцией.

2. for (int i = 1; i <= n; i += (i * 1.2)) В вашем случае решение также является логарифмическим решением, но оно не относится к основанию 2. Основой вашей логарифмической операции является 2.2, но в обозначении big-O оно сводится к O(log(n))