#c #arrays #string #char #cout
#c #массивы #строка #обуглить #cout
Вопрос:
Поэтому я пробовал базовую программу для печати префиксных подстрок строки (подстроки «»,»a»,»ab»,»abc» для строки «abc»), и она работала нормально:
void PrefixSubstrings(string s, int n){ coutlt;lt;"sub = "lt;lt;endl; // assumes empty subst as subst as well char sub[n 1]; for(int j=0;jlt;n;j ){ sub[j]= s[j] ; sub[j 1]=0 ; coutlt;lt;"sub = "lt;lt;sublt;lt;endl; }} Но потом я подумал о его временной сложности , это может показаться O(n) ,но потом я заметил, что со стороны
coutlt;lt;»sub = «lt;lt;sublt;;
Я не уверен, но требуется ли дополнительное O(n) для печати массива символов с использованием вышеуказанного метода и эффективного выполнения моей программы O(n^2) ?
Комментарии:
1.
char sub[n 1];— Это недопустимый C . Массивы в C должны иметь размер, обозначаемый выражением во время компиляции, а не значением во время выполнения. Вместо:std::vectorlt;chargt; sub(n 1);2. Да, его сложность будет квадратичной по длине строки.
3. @WaisKamal Я искал в сети, но не смог найти способ печатать массив символов в постоянное время . Итак , если я буду использовать строку вместо символа для хранения подстрок и печати, будет ли это происходить в постоянное время? Или есть какой-либо другой способ распечатать его в постоянное время ?
4. Почему вы ожидаете, что для печати строки потребуется одинаковое количество времени, независимо от того, сколько в ней символов?
5. Как вы можете печатать n символов за постоянное время? Это означало бы пропуск некоторых символов. Даже если вы используете строку, она будет выводить по одному символу за раз за кулисами.