[問題] 一題ipod shuffle 演算法問題
假設存了100首歌
這樣一首一首找 找到你要聽的歌
平均值是50
O(N)
假設用SHUFFLE 而且資料結構是10首一張專輯(或同個歌手等等)
這樣隨機選到你要聽的那個叢集的機率是10分之1
再來 最糟的情況是往下5或往上5 就可以找到要的歌
平均值是15
O(LOGN)
所以IPOD SHUFFLE 勝利
考慮BIG O時是不用考慮硬體時間的
所有的指令都當成一樣長度 且同樣執行時間
再來 他說的是使用者 使用上的演算法
不是給電腦TRACE的
如果100首歌 以10當成區間去RANDOM
這樣收尋到 其中一個區間機率為10分之ㄧ
也就是說 你運氣在不好 按到第10次 也該找到你要的區間了
這樣再平均 往下按5 或往上按5(調回連續播放模式) 就是你要找的歌
跟TREE或 ARRAY 沒什麼直接太大的關係 別往那邊想
而且成長的級數的確是LOGn
他想表達的是 沒螢幕並不會在找歌上造成太大的不便
換來的是 這款MP3 其他方面的優點
這樣對嗎? 這是我朋友的想法啦,不過我覺得怪怪的.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.123.220.24
CSSE 近期熱門文章
PTT數位生活區 即時熱門文章
