У меня есть длинный текст, сохраненный в StringBuilder, и я хочу получить какой-то конкретный элемент
StringBuilder builder = new StringBuilder();
//fill builder
int i = someNumber();
char ch = builder[i];
какова временная сложность последней инструкции (char ch = builder[i])? Это постоянно
O(1)
или это линейно?
O(i)
Это константа, так как вы указываете точное местоположение элемента, поэтому в данном случае O (1). Подробнее здесь Какова сложность этот простой фрагмент кода?
Согласно справочному источнику StringBuilder класс хранит строки в char Массив.
Доступ к этому массиву через средство получения свойств this[int index] выполняет несколько проверок и затем возвращает элемент массива:
internal char[] m_ChunkChars; // The characters in this block
//...more stuff
[System.Runtime.CompilerServices.IndexerName("Chars")]
public char this[int index] {
//
get {
StringBuilder chunk = this;
for (; ; )
{
int indexInBlock = index - chunk.m_ChunkOffset;
if (indexInBlock >= 0)
{
if (indexInBlock >= chunk.m_ChunkLength)
throw new IndexOutOfRangeException();
return chunk.m_ChunkChars[indexInBlock];
}
chunk = chunk.m_ChunkPrevious;
if (chunk == null)
throw new IndexOutOfRangeException();
}
}
//... more stuff
}
Таким образом, сложность составляет O (1) или постоянное время доступа.
char ch = builder[i] is O(1) .
Поскольку StringBuilder использовал индекс массива.
Если посмотреть на реализацию StringBuilder, это O (1), потому что используется char[]
//
//
// CLASS VARIABLES
//
//
internal char[] m_ChunkChars; // The characters in this block
internal StringBuilder m_ChunkPrevious; // Link to the block logically before this block
internal int m_ChunkLength; // The index in m_ChunkChars that represent the end of the block
internal int m_ChunkOffset; // The logial offset (sum of all characters in previous blocks)
internal int m_MaxCapacity = 0;
