Какова сложность приведенного ниже кода по отношению к памяти?

Question

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

    private void reverse(String strToRevers) 
    {
        if(strToRevers.length() == 0)
        {
            return ;
        }
        else 
        {
            reverse(strToRevers.substring(1));
            System.out.print(strToRevers.charAt(0));
        }
    }

Если учитывать фактор памяти, то сложность приведенного выше кода для строки из n символов равна O (n ^ 2). Объяснение приведено для строки, состоящей из n символов, приведенная ниже функция будет вызываться рекурсивно n-1 раз, и каждый вызов функции создает строку из одного символа (stringToReverse.charAT (0)). Следовательно, это n * (n-1) * 2, что означает o (n ^ 2). Дайте мне знать, если это правильно?

Answer 1

Следовательно, это n * (n-1) * 2, что означает o (n ^ 2). Дайте мне знать, если это правильно?

Почти: это n * (n-1) / 2, а не *2, что также равно O (n ^ 2). Обратите внимание, что o (n ^ 2) (little-O) означает что-то еще , поэтому различие важно.

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

Answer 2

Похоже на Java, поэтому не O (n ** 2). Это потому, что строки совместно используют основные буферы последовательности символов; они могут сделать это, потому что они являются неизменными объектами.

Но это O (n) в пространстве стека. Это не хорошо. Лучше выделить изменяемый рабочий буфер символов, обратить строку в нее, а затем распечатать весь лот сразу.