Что такое большой O этой подстроки + конкатенация al go? - PullRequest
Новая
       5

Что такое большой O этой подстроки + конкатенация al go?

0 голосов
/ 02 марта 2020

Я борюсь со сложностью Big O, и этот тип al go всегда смущал меня. Мы перебираем каждое число здесь в 2 циклах, поэтому его O (n ^ 2). Но внутри каждой итерации циклов у нас есть подстрока + конкатенация. Из того, что я понимаю, конкатенация оптимизирована компилятором для использования по существу строкового буфера. Подстрока считается только 4 * n? Таким образом, общее количество вычислений равно n n (n + (4 * n)) ИЛИ O (n ^ 3). (n + (4 * n)) происходит от конкатенации + 4 подстроки. Правильна ли моя оценка?

Я пытаюсь решить эту проблему: https://leetcode.com/problems/maximum-swap

public int maximumSwap(int num) {
        int biggestNum = num;
        String sNum = String.valueOf(num);
        for(int i = 0; i < sNum.length()-1; i++) {
            for(int j = i+1; j < sNum.length(); j++) {
                // 27364
                String jSuffix = j == sNum.length()-1 ? "" : sNum.substring(j+1);
                int newNum = Integer.valueOf(sNum.substring(0, i) + sNum.charAt(j) + sNum.substring(i+1, j) + sNum.charAt(i) + jSuffix);
                if(newNum > biggestNum) biggestNum = newNum;
            }
        }
        return biggestNum;
    }

Ответы [ 2 ]

1 голос
/ 02 марта 2020

Это правильно, даже если конкатенация строк не была оптимизирована компилятором.

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

Если аргумент был BigInteger анализ во время выполнения станет более значимым. Тогда вам также придется подумать о том, сколько времени займет сравнение или Integer.valueOf(string) (точнее, BigInteger эквивалент new BigInteger(string)). Последнее, вероятно, в O (n ^ 2), если вы дадите ему ввод с n цифрами, что означает, что весь алгоритм будет работать в O (n ^ 4).

0 голосов
/ 02 марта 2020

Что такое большой O этой подстроки + конкатенация al go?

--- ИМХО, + сложность времени операции O (n).

Из того, что я понимаю, компилятор оптимизировал компилятор для использования по существу строкового буфера.

--- Мы не можем предполагать, что компилятор выполнит оптимизацию, см. эта ссылка . Даже если это так, он компилируется в StringBuider, а не StringBuffer. Они разные. Если компилятор не выполняет оптимизацию, время должно быть O (n), он будет копировать всю строку для каждой + операции. См. эту ссылку.

подстрока просто считается как 4 * n? Таким образом, общее количество вычислений равно nn (n + (4 * n)) ИЛИ O (n ^ 3). (n + (4 * n)) происходит от конкатенации + 4 подстроки. Является ли моя оценка правильной?

--- ИМХО, Java Строковые операции, такие как подстрока, будут стоить O (n) времени, см. эту ссылку и + операция также стоит O (n), временная сложность int newNum = Integer.valueOf(sNum.substring(0, i) + sNum.charAt(j) + sNum.substring(i+1, j) + sNum.charAt(i) + jSuffix); должна быть O (6n) (4n для 4 +, 2n для 2 substring)

...