史萊姆論壇

返回   史萊姆論壇 > 專業主討論區 > 程式語言討論區
忘記密碼?
註冊帳號 論壇說明 標記討論區已讀

歡迎您來到『史萊姆論壇』 ^___^

您目前正以訪客的身份瀏覽本論壇,訪客所擁有的權限將受到限制,您可以瀏覽本論壇大部份的版區與文章,但您將無法參與任何討論或是使用私人訊息與其他會員交流。若您希望擁有完整的使用權限,請註冊成為我們的一份子,註冊的程序十分簡單、快速,而且最重要的是--註冊是完全免費的!

請點擊這裡:『註冊成為我們的一份子!』

Google 提供的廣告


發文 回覆
 
主題工具 顯示模式
舊 2016-10-09, 01:00 PM   #1
alanniok 帥哥
註冊會員
榮譽勳章

勳章總數
UID - 369540
在線等級: 級別:3 | 在線時長:27小時 | 升級還需:5小時級別:3 | 在線時長:27小時 | 升級還需:5小時級別:3 | 在線時長:27小時 | 升級還需:5小時
註冊日期: 2015-06-21
文章: 54
精華: 0
現金: 83 金幣
資產: 83 金幣
預設 疑問 - 有關空間複雜度的問題



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


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

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

一般可以用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],但是卻說此程式的空間複雜度不受輸入影響??
alanniok 目前離線  
送花文章: 71, 收花文章: 17 篇, 收花: 22 次
回覆時引用此帖
舊 2016-10-10, 09:08 PM   #2 (permalink)
管理版主
 
mini 的頭像
榮譽勳章
UID - 4144
在線等級: 級別:85 | 在線時長:7602小時 | 升級還需:138小時級別:85 | 在線時長:7602小時 | 升級還需:138小時級別:85 | 在線時長:7602小時 | 升級還需:138小時級別:85 | 在線時長:7602小時 | 升級還需:138小時級別:85 | 在線時長:7602小時 | 升級還需:138小時
註冊日期: 2002-12-07
文章: 11722
精華: 0
現金: 22695 金幣
資產: 3020025 金幣
預設



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

不同程式語言會有不同的 複雜度
你貼的是 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 編輯.
mini 目前離線  
送花文章: 1677, 收花文章: 7371 篇, 收花: 25760 次
回覆時引用此帖
向 mini 送花的會員:
alanniok (2016-10-13)
感謝您發表一篇好文章
舊 2016-10-13, 08:01 AM   #3 (permalink)
註冊會員
榮譽勳章

勳章總數
UID - 369540
在線等級: 級別:3 | 在線時長:27小時 | 升級還需:5小時級別:3 | 在線時長:27小時 | 升級還需:5小時級別:3 | 在線時長:27小時 | 升級還需:5小時
註冊日期: 2015-06-21
文章: 54
精華: 0
現金: 83 金幣
資產: 83 金幣
預設

感謝!! 寫的很清楚~~~
所以原來這是有點過時的觀念了嗎(空間複雜度)?
這是我現在在大學念資工系遇到的內容哈哈...
alanniok 目前離線  
送花文章: 71, 收花文章: 17 篇, 收花: 22 次
回覆時引用此帖
舊 2016-10-13, 09:09 AM   #4 (permalink)
管理版主
 
mini 的頭像
榮譽勳章
UID - 4144
在線等級: 級別:85 | 在線時長:7602小時 | 升級還需:138小時級別:85 | 在線時長:7602小時 | 升級還需:138小時級別:85 | 在線時長:7602小時 | 升級還需:138小時級別:85 | 在線時長:7602小時 | 升級還需:138小時級別:85 | 在線時長:7602小時 | 升級還需:138小時
註冊日期: 2002-12-07
文章: 11722
精華: 0
現金: 22695 金幣
資產: 3020025 金幣
預設

引用:
作者: alanniok 查看文章
所以原來這是有點過時的觀念了嗎(空間複雜度)?
這是我現在在大學念資工系遇到的內容哈哈...
也不是這樣說啦~
(畢竟幾十年前記憶體不是這麼便宜,而且在64位元世代後更無須特別節儉記憶體的不足問題)

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

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

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

此帖於 2016-10-13 01:02 PM 被 mini 編輯.
mini 目前離線  
送花文章: 1677, 收花文章: 7371 篇, 收花: 25760 次
回覆時引用此帖
向 mini 送花的會員:
alanniok (2016-10-13)
感謝您發表一篇好文章
舊 2016-10-13, 07:57 PM   #5 (permalink)
註冊會員
榮譽勳章

勳章總數
UID - 369540
在線等級: 級別:3 | 在線時長:27小時 | 升級還需:5小時級別:3 | 在線時長:27小時 | 升級還需:5小時級別:3 | 在線時長:27小時 | 升級還需:5小時
註冊日期: 2015-06-21
文章: 54
精華: 0
現金: 83 金幣
資產: 83 金幣
預設

確實老師有說到一般比較重視時間複雜度,只有在資源比較緊的環境工作時才會優先考慮空間複雜度
ex.手機or遙控器之類記憶體較小的地方
alanniok 目前離線  
送花文章: 71, 收花文章: 17 篇, 收花: 22 次
回覆時引用此帖
發文 回覆


主題工具
顯示模式

發表規則
不可以發文
不可以回覆主題
不可以上傳附加檔案
不可以編輯您的文章

論壇啟用 BB 語法
論壇啟用 表情符號
論壇啟用 [IMG] 語法
論壇禁用 HTML 語法
Trackbacks are 禁用
Pingbacks are 禁用
Refbacks are 禁用


所有時間均為台北時間。現在的時間是 06:31 PM


Powered by vBulletin® 版本 3.6.8
版權所有 ©2000 - 2018, Jelsoft Enterprises Ltd.


SEO by vBSEO 3.6.1