推 privatewind:這有錯誤…i被宣告定義只有一次...所以它佔用到的空間 09/27 13:37
→ privatewind:只有4byte 跟n不成關係…所以出題的人沒啥問題吧XD 09/27 13:38
推 privatewind:喔喔~你是說i 需要用多少個bit去存喔?...囧 抱歉~ 09/27 13:41
※ 引述《privatewind (傷神客)》之銘言：
: ※ 引述《bernachom (Terry)》之銘言：
: : 請教一下
: : Does bubblesort requires additional storage depending on input size n?
: ^^^^^^^^^^^^^^^^^^^^^^^^^
: : Explain your answer.
: 這題的重點是depending on input size n
: swap也是要用到額外的空間，但是使用量並不依賴n
: int bubblesort(int data[],int* beg,int* end){
: int temp;
: for(int i=0 ; i<end-beg;++i){
如果從計算理論的角度來看，變數i depends on input size n。
因為i至少要可以保存 0 ~ end-beg 範圍內所有的值。
所以至少需要lg (end-beg)個bit。
--
不過我想出題的人應該沒有想那麼多..
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50