在 stringbuilder 中查看项目的时间复杂度 - C#

Question

我在 StringBuilder 中保存了一些长文本，我想获取一些特定的项目

StringBuilder builder = new StringBuilder();
//fill builder
int i = someNumber();
char ch = builder[i];

最后一条指令 (char ch = builder[i]) 的时间复杂度是多少？是否恒定

O(1)

还是线性的？

O(i)

Answer 1

它是一个常量，因为在这种情况下，您要给出准确的位置才能获得 element.So O(1)。更多细节在这里 What is the complexity of this simple piece of code?

Answer 2

char ch = builder[i] 是 O(1) .

因为 StringBuilder 使用了数组索引。

Answer 3

根据 Reference Source，StringBuilder class 将字符串存储在字符数组中。

通过属性 getter this[int index] 访问此数组进行一些检查，然后 returns 数组项：

    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) 或常数访问时间。

Answer 4

查看 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;

在 stringbuilder 中查看项目的时间复杂度 - C#

Time-complexity of looking at item in stringbuider - C#

c#

stringbuilder

time-complexity