|
論壇說明 | 標記討論區已讀 |
歡迎您來到『史萊姆論壇』 ^___^ 您目前正以訪客的身份瀏覽本論壇,訪客所擁有的權限將受到限制,您可以瀏覽本論壇大部份的版區與文章,但您將無法參與任何討論或是使用私人訊息與其他會員交流。若您希望擁有完整的使用權限,請註冊成為我們的一份子,註冊的程序十分簡單、快速,而且最重要的是--註冊是完全免費的! 請點擊這裡:『註冊成為我們的一份子!』 |
|
主題工具 | 顯示模式 |
2016-10-09, 01:00 PM | #1 |
註冊會員
|
疑問 - 有關空間複雜度的問題
-------------------- 閱讀本主題的最佳解答 -------------------- 首先抱歉我不知道這個是不是該在這裡問?? 就是資料結構中有個東西叫 “空間複雜度” 。 一般可以用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],但是卻說此程式的空間複雜度不受輸入影響?? |
送花文章: 75,
|
2016-10-10, 09:08 PM | #2 (permalink) |
管理版主
|
所謂 空間複雜度 就是指 記憶體使用量在"執行階段" 會出現"多" 「不可預期」的程度 或稱 需考量的程度 (越複雜就越難掌控,程式容易出現溢位錯誤,也就是異常終結,甚至形成駭客進入的罩門) 不同程式語言會有不同的 複雜度 你貼的是 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作變化 而且呈現等比級數增加 ========== 說起來 "空間複雜度" 這是早期的觀念 現代程式語言 語法設計越來越嚴僅 加上強化 容錯處理 除非你要設計小而美的軟體(比如行動裝置記憶體小就要考量這) 不然很少人會考量這麼多 此帖於 2016-10-10 09:40 PM 被 mini 編輯. |
送花文章: 2007,
|
向 mini 送花的會員:
|
alanniok (2016-10-13)
感謝您發表一篇好文章 |
2016-10-13, 09:09 AM | #4 (permalink) |
管理版主
|
也不是這樣說啦~
(畢竟幾十年前記憶體不是這麼便宜,而且在64位元世代後更無須特別節儉記憶體的不足問題) 寫這麼久程式都是先求有(實現功能) 再求好(優化程式碼) 除非你一開始就設計規劃嚴僅 (或經驗足一開始就能腦內規劃好) 所以 記憶體使用量不是排在前頭的考量 (效能就是時間代表金錢,"記憶體使用量"是為了實現而存在的可犧牲者) 寫久了會發現一點 記憶體使用量往往會與執行效能成正比 (因為放在記憶體裡總是比後來讀取 與再運算來的快,特別是累積運算後感覺更明顯) 以上總總 所以才認為 空間複雜度的問題 是 早期的觀念 研發或研究的學者會比較在意 ======== 這個空間複雜度還有一點比較重要 就是提醒自己避免無限回圈的寫作 記憶體的使用放在裡頭程式就會有灌爆系統效能的可能 此帖於 2016-10-13 01:02 PM 被 mini 編輯. |
送花文章: 2007,
|
向 mini 送花的會員:
|
alanniok (2016-10-13)
感謝您發表一篇好文章 |