疑問 - 有關空間複雜度的問題

[alanniok]

--------------------
閱讀本主題的最佳解答
--------------------


首先抱歉我不知道這個是不是該在這裡問？？

就是資料結構中有個東西叫 “空間複雜度” 。

一般可以用S(P)=C+Sp(I)表示。其中C是固定項，Sp(I)是隨輸入不同結果會不同的項。

然後有個程式長這樣：
float sum(float list[ ], int n)
{
float tempsum = 0;
int i;
for (i = 0; i<n; i++)
tempsum += list [i];
return tempsum;
}

請問為什麼他的Sp(I)=0呢？？
明明隨著n越大，會有越多個list[i]，但是卻說此程式的空間複雜度不受輸入影響？？

[mini]

所謂 空間複雜度 就是指
記憶體使用量在"執行階段"
會出現"多" 「不可預期」的程度
或稱
需考量的程度
(越複雜就越難掌控，程式容易出現溢位錯誤，也就是異常終結，甚至形成駭客進入的罩門)

不同程式語言會有不同的 複雜度
你貼的是 C/C++
需注意兩點
1.在 C語言上沒有所謂的 變動陣列 (除非你用鏈結來取代傳統陣列)
也就是在宣告時你要盡量宣告出足以應付的陣列大小
P.S.這一點就解釋你的疑問「明明隨著n越大，會有越多個list[i]...」，n也不能超過 宣告的陣列長度
2.存放 計算結果 的變數類型 須考量兩者誰大誰小(能代表的量)，需考量用大者來當 存放計算結果之變數

舉個例：a=a+f
如要說複雜度從1~10分級的話 (越高越複雜)
其複雜度可以說是 2
因為只需考量變數 a可以容納相加結果就沒問題 (比如 uint32 可以代表的量範圍是 0~FFFFFFFF)
而
狀況1: 如 f 是變數複雜度會提升一級(但也是固定值，空間複雜度不變)
狀況2: 如 f 是常數那複雜度會變低一級(同樣)
狀況3: 如 f 是陣列那相當於狀況1
你舉的 tempsum += list [i]; 就是狀況3
因為一個float變數就能應付 (相加結果不要大於小於 float變數能代表的量就好了)

P.S.
tempsum 與 list[] 都是 float變數，所以複雜度單純
如是不同類型變數，tempsum需為大容量變數
比如 float能裝的下int代表量，如tempsum是int、list[]是float就會出問題

那什麼情況複雜度會變化
比如 VB語言的string變數
string變數可以不斷的串連/縮減 變更
例子：
Dim s as string
for i=0 to n
s=s & cstr(i)
next
n是輸入值的話
空間複雜度就會受輸入影響，因為記憶體使用空間會隨n作變化
而且呈現等比級數增加

==========
說起來 "空間複雜度" 這是早期的觀念
現代程式語言 語法設計越來越嚴僅
加上強化 容錯處理
除非你要設計小而美的軟體(比如行動裝置記憶體小就要考量這)
不然很少人會考量這麼多

[alanniok]

感謝!! 寫的很清楚~~~
所以原來這是有點過時的觀念了嗎(空間複雜度)?
這是我現在在大學念資工系遇到的內容哈哈...

[mini]

作者: alanniok

所以原來這是有點過時的觀念了嗎(空間複雜度)?
這是我現在在大學念資工系遇到的內容哈哈...

也不是這樣說啦～
(畢竟幾十年前記憶體不是這麼便宜，而且在64位元世代後更無須特別節儉記憶體的不足問題)

寫這麼久程式都是先求有(實現功能) 再求好(優化程式碼)
除非你一開始就設計規劃嚴僅 (或經驗足一開始就能腦內規劃好)
所以
記憶體使用量不是排在前頭的考量
(效能就是時間代表金錢，"記憶體使用量"是為了實現而存在的可犧牲者)

寫久了會發現一點
記憶體使用量往往會與執行效能成正比
(因為放在記憶體裡總是比後來讀取 與再運算來的快，特別是累積運算後感覺更明顯)
以上總總
所以才認為 空間複雜度的問題 是 早期的觀念
研發或研究的學者會比較在意

========
這個空間複雜度還有一點比較重要
就是提醒自己避免無限回圈的寫作
記憶體的使用放在裡頭程式就會有灌爆系統效能的可能

[alanniok]

確實老師有說到一般比較重視時間複雜度，只有在資源比較緊的環境工作時才會優先考慮空間複雜度
ex.手機or遙控器之類記憶體較小的地方