Блог

Главная - Вопросы по программированию - Являются ли временные и пространственные сложности для моего алгоритма проверки правильности перестановок двух строк друг друга?

Являются ли временные и пространственные сложности для моего алгоритма проверки правильности перестановок двух строк друг друга?

#java #time-complexity #big-o

Вопрос:

     /*
    Returns true is the two strings are permutations of each other.
    Time Complexity; O(nlog n) -> because of the java utils array sort
    Space Complexity; O(1)
 */
public boolean isPermutationOptimized(String one, String two) {
    if (one.length() != two.length()) {
        return false;
    }
    return sort(one).equals(sort(two));
}

public String sort(String s) {
    char[] c = s.toCharArray();
    java.util.Arrays.sort(c);
    return new String(c);
}

Я считаю, что временная сложность равна O(nlogn) из-за сортировки массива java.utils, а сложность пространства постоянна.

Комментарии:

1. Сложность пространства неверна.

2. Если one бы и two было по 10 МБ или 100 МБ каждый, сколько памяти потребовалось бы алгоритму? Какие строки в вашем фрагменте кода потребовали бы большого выделения места?

3. Примечание O(n) . В этом случае вы также можете выполнить сортировку.

4. Как я могу выполнить сортировку за O(n) время?

5. @DavisWard Сортировка по радиусу и сортировка по счету часто используются для сортировки строк и наборов небольших целых чисел. Это исключение из типичного O(n log n) ожидания сортировки, потому что вы можете просто посчитать/увеличить (O(1)) для каждого символа (O(n)) и воспроизвести его за время O(n k) с k таким количеством сегментов (65536, для значений символов 65536).

Ответ №1:

Временная сложность составляет O(nlogn) как в среднем, так и в худшем случае. Пространственная сложность Timsort (используемый алгоритм сортировки) требует дополнительного пространства O(n): это не постоянная сложность, а линейная сложность. Некоторые ссылки: https://ericmervin.medium.com/what-is-timsort-76173b49bd16

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

Метки: