java - "builder.replace"是什么类型的复杂性？

Question

我正在 HackerRank 上做 stairCase 谜题，有人提到它无法在小于 o(n^2) 的情况下解决。拼图链接:https://www.hackerrank.com/challenges/staircase/problem

我使用嵌套循环解决了它，但另一个人发布了以下解决方案:

 StringBuilder builder = new StringBuilder();
    for (int i = 0; i <n ; i++) 
        builder.append(" ");
    int j = 0;

for (int i = 1; i <=n; i++) 
{
        builder.replace(builder.length()-i,          
        builder.length() - j, "#");
        System.out.println(builder);
        j++;
}

我想知道它也是 o(n^2) 吗？ builder.replace 是否像 for 循环一样遍历所有字符串？

谢谢你的时间

Answer 1

是的，builder.replace 将使用具有 O(n) 复杂度的 native 数组复制调用。所以对于外层循环，整体是 O(n^2)。因为输出的长度为 O(n^2)，所以任何生成它的程序都至少具有那个时间复杂度。