iT邦幫忙

0

(已解決)Java 字串串接 的時間複雜度問題

  • 分享至 

  • xImage

在leetcode看教學文章的時候遇到了以下問題
不太確定自己的理解對不對
想請教有沒有人可以更清楚的說明

public class Main {
    public static void main(String[] args) {
        String s = "";
        int n = 10000;
        for (int i = 0; i < n; i++) {
            s += "hello";
        }
    }
}

In Java, since the string is immutable, concatenation works by first allocating enough space for the new string, copy the contents from the old string and append to the new string.

Therefore, the time complexity in total will be:
5 + 5 × 2 + 5 × 3 + … + 5 × n
= 5 × (1 + 2 + 3 + … + n)
= 5 × n × (n + 1) / 2,

which is O(n2). (這個2是平方)
以上是leetcode上的原文說明

以下是我自己的理解:
以i=0來舉例
s+="hello" 相加前會先創建一個長度為 他們兩個長度相加的空間準備用來存放
s一開始長度0
"hello" 長度5
所以相加前 會先建立一個長度為5的空間
然後"逐個"把h e l l o 一個一個放進去空間裡面
所以這邊就會迭代5次
完成後此時s就等於"hello"
i=1的時候
創建長度10的空間存放
s=s+"hello"
再次把s跟"hello" 逐個拆成字元丟進去空間裡面
所以會重複2*5次

如此重複n次得到:
5 + 5 × 2 + 5 × 3 + … + 5 × n
= 5 × (1 + 2 + 3 + … + n)
= 5 × n × (n + 1) / 2,

請問我這樣理解對嗎 我重點就是不太確定那個5
是不是因為逐個把字元丟進去所產生的

圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

1 個回答

0
海綿寶寶
iT邦大神 1 級 ‧ 2022-05-17 08:40:02
最佳解答

對,5 是你想的那樣

另外提供參考
Google 的結果,大部份都是在討論
1.immutable
2.N[sup]2[/sup]

沒什麼人在乎那個 5
參考連結

Liang iT邦新手 4 級 ‧ 2022-05-17 11:42:37 檢舉

感謝你的回答~
我Google也有看到很多人在討論immutable的部分
真的沒人在討論我疑問的部分 才上來發問
我一開始以為字串相加 是分別把兩個字串"一次性"放進新空間
也就是每次相加 作2次放進去的操作
loop n次後 應該要是O(2*n)

我是根據解答才想說 那可能就是因為逐個放進去的關係
但又不是很確定
原來是因為String底層是用byte[]的關係

我要發表回答

立即登入回答