Эта программа рекурсивно печатает все возможные комбинации данной строки Я смущен утверждением внутри цикла for, который рекурсивно вызывает себя. Это неявный п * п, где п длина строкиКакова будет сложность следующей программы
public static void getStringCombination(String prefix, String str) {
System.out.println(prefix);
for (int i = 0; i < str.length(); i++)
getStringCombination(prefix + str.charAt(i), str.substring(i + 1));
}
Она должна быть близка к O (n2), однако мы не можем сказать, что это точное, потому что это случай рекурсии.
Хотя у меня лично всегда были проблемы с определением таких вещей, я должен был бы сказать, что это факториал. Первый намек заключается в том, что вы печатаете all the possible combination, что является более или менее факториалом, если я правильно помню свои математические школы. Второй совет: вы выполняете цикл for по всей строке, в которой вы выполняете рекурсивный вызов, поэтому первый вызов вы будете выполнять N рекурсивных вызовов, а затем для следующего рекурсивного вызова вы будете делать N-1 рекурсивные звонки и т. д.
Должен сказать, что, сказав это, я как бы сомневаюсь в себе и факте, действительно ли он печатает все возможные комбинации ... Я вполне уверен, что он не печатает комбинации, которые связаны с последние символы находятся перед первыми символами. Это может сделать мое заявление о том, что оно является факториалом неправильным, но я не могу сказать, что я уверен в этом.
EDIT
После прочтения ответа и тестирование @Ben С., я абсолютно уверен, что ваш пример O (2^п) и моя мысль, что «исправить» Бен С. является O (n!), Однако кажется, что я ошибаюсь, это на самом деле выше. Боюсь, я не могу объяснить, почему ваш пример 2^n, хотя и все еще обдумывал это сам.
Что вы имеете в виду по сложности? И что вы пробовали до сих пор? –
Я имею в виду сложность выполнения. После нескольких размышлений я все еще запутался, является ли он линейным или неявным квадратичным – user2861320
Поскольку цикл for вызывает метод снова, который далее вызывает цикл for и т. Д. – user2861320