Где мы проводим грань между O (1) и O (n) как на практике, так и в теории? - PullRequest
Новая
       31

Где мы проводим грань между O (1) и O (n) как на практике, так и в теории?

0 голосов
/ 13 января 2019

Предположим, у нас есть следующая проблема вместе с java-методом, который может помочь.

Пользователь вводит пароли длиной от 5 до 35 символов включительно. Нам нужно убедиться, что они не повторяют один и тот же символ 3 раза подряд. 

boolean has3CharsInARow(char [] password){
  for(int left=0, middle=1, right=2; right < password.length; left++, middle++, right++){
    if(password[left]==password[middle] && password[middle]==password[right]){
      return true;
    }
  }
  return false;
}

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

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

Каков аргумент для O (1)? Хорошо, учитывая контекст, мы знаем, что есть ограничения на пароль, он может не более быть длиной 35 символов. Таким образом, в худшем случае мы не находим 3 повторяющихся символа, мы сканируем O (34) 33 на правильные индексы от 2 до 34 и еще 1 потому что когда право равно 35, а затем мы выходим из охраны цикла и, наконец, возвращаем ложь. Поскольку 34 является константой, в общем случае мы говорим, что O (34) = O (1) является постоянной сложностью по времени.

Каков аргумент для O (n)? Хорошо, мы заботимся о том, как эффективность использования времени ведет себя при увеличении длины ввода. Если мы Предположим, что T (n) - время выполнения has3CharsInARow, и мы можем сказать, что T растет линейно пропорционально для каждой единицы измерения или увеличения длины пароля. Так что T находится в классе функций O (n).

Где мы проводим линию между O (1) и O (n)?

Edit: Поскольку один из ответчиков написал O (n), значит ли это, что этот эквивалентный метод тоже O (n)? 

boolean has3CharsInARow(char [] password){
  switch(password.length){
    case 0:
    case 1:
    case 2:
        return false;
    case 3: return password[0] == password[1] && password[1] == password[2];
    case 4: return password[0] == password[1] && password[1] == password[2] ||
            password[1] == password[2] && password[2] == password[3];
    ...
    case 35: return ...;

  }
}

1 Ответ

0 голосов
/ 13 января 2019

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

Я думаю, что путаница возникает из-за того, что люди не понимают, что означает большая буква О и как ее интерпретировать. Вы говорите (я перефразирую): «но если я ограничу размер входных данных константой, то сложность действительно будет постоянной, нет?» И ответ нет. Временная сложность - это «описание» того, как увеличивается время выполнения алгоритма по мере роста входных данных. Это «описание» все еще верно, даже если диапазон ввода составляет [5, 35] или [5, Integer.MAX_VALUE] или [5, ∞). Это (со) отношение между временем выполнения и размером ввода.

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

Давайте посмотрим, как сложность времени может помочь вам в вашем случае:

Сложность по времени линейна. При таком маленьком входном размере вы можете сделать разумный вывод, что алгоритм в порядке, и вам не нужно слишком беспокоиться об этом.

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

...