Блог

Я пытаюсь понять временную сложность для этого кода, который вычисляет IP-адреса для данной строки, разделив строку на 4 части. Каждая часть разделена точкой, т. е. .

 public List<String> restoreIpAddresses(String s, int parts) {

    List<String> result = new ArrayList<>();
    if (parts == 1) {
        if (isValidPart(s)) result.add(s);
        return resu<
    }
    
    for (int i = 0; i < s.length(); i  ) {
        String first = s.substring(0, i);
        if (!isValidPart(first)) {
            continue;
        }
        
        List<String> previous = restoreIpAddresses(s.substring(i, s.length()), parts - 1);
        
        for (String str: previous) {
            StringBuilder sb = new StringBuilder();
            result.add(first   "."   str);
        }
    }        
    
    return resu<
    
}

private boolean isValidPart(String part) {
    if ( (part.length() > 1 amp;amp; part.startsWith("0")) || 
         (part.length() > 3) || (part.length() == 0)
         (Integer.valueOf(part) > 255) ) return false;
      return true;
    }
}
 

Поскольку цикл for O(n) равен , n-это длина строки, и на каждой итерации цикл for выполняется для подстроки, переданной в родительском цикле for, поэтому O(n - 1) . Так что по этой логике временная сложность должна быть n(n-1)(n-2) ....1 , т. е. n! в худшем случае, верно?

Однако, если я оглянусь (например, здесь или здесь), я увижу, что люди публикуют постоянную временную сложность. Я не в состоянии понять. Кто-нибудь может помочь мне разобраться в этом?

Учтите, что для генерации IP-адресов из приведенного выше алгоритма у нас есть два ограничения.

1. Допустимый IP-адрес от 0 до>255. Это можно оценить в течение постоянного времени.
2. Там будет 4 октета. Таким образом, строка вопроса должна быть разделена на 4 части.

Теперь рассмотрим строку 111 111 111 111 длины 12

1. Сколько способов вы можете сформировать первый октет? => минимум 1 , максимум 3 варианта из 12 символов. complexity:- O(3)
2. Сколько способов вы можете сформировать второй октет? => минимум 0 максимум 3 способа из 9 символов, учитывая, что в первом октете используются 3 символа. complexity:- O(3)
3. Сколько способов вы можете сформировать третий октет? => минимум 0 максимум 3 способа из 6 символов, учитывая, что 6 символов используются первым и вторым октетом. complexity:- O(3)
4. Сколько способов вы можете сформировать четвертый октет из оставшихся символов? => Существует только один способ сформировать октет из оставшихся 3 символов. учитывая, что в первом, втором и третьем октете используется 9 символов. O(1)

Расчет временной сложности.

 Time Complexity = product of complexities of each recursive function
                = O(3)*O(3)*O(3)*O(1)
                = 3*O(3) = O(1) = [constant-time] complexity

 

Таким образом, независимо от того, какую строку вы будете вводить в качестве входных данных, все действительные IP-адреса могут быть подсчитаны в 27 итерациях. Поэтому этот алгоритм является постоянным по времени O(1) .

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

 
public static List<String> restoreIpAddresses(String s, int position, int parts) {

        List<String> result = new ArrayList<>();
        // O(1) time complexity
        if (parts == 1) {
            if (position < s.length() amp;amp; isValidPart(s.substring(position))) {
                result.add(s.substring(position));
            }
            return resu<
        }

        // Iterate only thrice in each recursive function. O(3) time complexity
        for (int i = position; i <= position   3; i  ) {
            if (i > s.length()) {
                continue;
            }

            String first = s.substring(position, i);
            if (!isValidPart(first)) {
                continue;
            }

            List<String> previous = restoreIpAddresses(s, i , parts - 1);

            for (String str : previous) {
                StringBuilder sb = new StringBuilder();
                result.add(first   "."   str);
            }
        }

        return resu<

    }

 

Обратите внимание, что приведенный выше алгоритм является одним из примеров классического backtracking problems . Из вики.

Обратное отслеживание-это общий алгоритм поиска решений некоторых вычислительных задач, в частности проблем с удовлетворением ограничений, который постепенно создает кандидатов для решений и отбрасывает кандидата («обратное отслеживание»), как только он определяет, что кандидат не может быть завершен до допустимого решения

PS:- Пример 111 111 111 111 является крайним примером, и 111.111.111.111 из этой строки может быть сформирован только один действительный IP-адрес. Однако оценка цикла/рекурсии будет выполняться максимум 81 раз.