Как пространственная сложность этого кода O (n)?

-2

public static boolean isUniqueChars2(String str) { 
     boolean[] char_set = new boolean[256]; 

     for (int i = 0; i < str.length(); i++) { 
      int val = str.charAt(i); 
      if (char_set[val]) 
       return false; 

      char_set[val] = true; 
     } 

     return true; 
    }

источник

2013-09-02 c2h5oh

Это не так. Это 'O (1)'. –

'new boolean [str.length()]' не имеет смысла ... – Betlista

@TedHopp - если бы он это сделал, его программа сработала бы для строки длиной не более 65 символов, содержащих букву «A». IOW, это предложение не является педагогическим. –

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

источник

2013-09-02 15:25:37 DDW

Я думаю, что временная сложность также O (1): никогда не будет более ~ 26 шагов, в зависимости от кодировки и наличия специальных символов –

Не считая входной строки, код имеет O(1) сложность пространства. Он потребляет постоянное пространство, независимо от ввода.

Сложность времени также равна O(1), так как цикл никогда не выполнит более 256 шагов.

источник

2013-09-02 15:24:34 NPE

Просто интересно, есть ли «худший случай»? – Betlista

@Betlista - Функция завершается, когда найден первый повторяющийся символ или вход исчерпан. Не повторяющиеся символы - наихудший случай. (Обратите внимание, однако, что по принципу [принцип пикника] (http://en.wikipedia.org/wiki/Pigeonhole_principle) не может быть более 256 уникальных символов.) –

Технически цикл должен выйти после 256 итераций , независимо от входной строки, поэтому это худшее время O (1). – delnan

Как пространственная сложность этого кода O (n)?

ответ

Смежные вопросы