衡量代碼運行效率的重要因素之復雜度

復雜度是衡量代碼運行效率的重要的度量因素,一般而言,代碼執(zhí)行過程中會消耗計算時間和計算空間,這里我們需要衡量的就是時間復雜度和空間復雜度.

  • 復雜度是一個關于輸入數(shù)據(jù)量n的函數(shù),O(n)表示的是復雜度與計算實例的個數(shù)n線性相關;O(logn)表示的是復雜度與計算實例的個數(shù)n對數(shù)相關.
  • 復雜度與具體的常系數(shù)無關.
  • 多項式級的復雜度相加的時候,選擇高者作為結(jié)果.
  • O(1)表示一個特殊復雜度,表示某個任務通過有限可數(shù)的資源即可完成,與輸入數(shù)據(jù)量n無關.

經(jīng)驗結(jié)論:
1.一個順序結(jié)構的代碼,時間復雜度是O(1)
2.二分查找(二分策略),時間復雜度市O(logn)
3.一個簡單的for循環(huán),時間復雜度是O(n)
4.兩個順序執(zhí)行的for循環(huán),時間復雜度O(n) + O(n) = O(2n),其實也是O(n)
5.兩個嵌套的for循環(huán),時間復雜度是O(n2)

高效代碼要采用盡可能低的時間復雜度和空間復雜度去完成開發(fā).
1.降低時間復雜度的方法有 遞歸绍昂、二分法氮发、排序算法、動態(tài)規(guī)劃等咖摹。
2.降低空間復雜度通常需要圍繞數(shù)據(jù)結(jié)構進行研究。

降低復雜度的經(jīng)驗結(jié)論:

1寇壳、暴力破解仿荆,在沒有任何時間、空間約束下怎抛,完成代碼任務的開發(fā)。
2芽淡、無效操作處理马绝,將代碼中的無效計算、無效存儲剔除吐绵,降低時間和空間復雜度迹淌。
3、時空轉(zhuǎn)換己单,設計合理的數(shù)據(jù)結(jié)構唉窃,完成時間復雜度向空間復雜度的轉(zhuǎn)移。

?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末纹笼,一起剝皮案震驚了整個濱河市纹份,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌廷痘,老刑警劉巖蔓涧,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異笋额,居然都是意外死亡元暴,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進店門兄猩,熙熙樓的掌柜王于貴愁眉苦臉地迎上來茉盏,“玉大人,你說我怎么就攤上這事枢冤○蹋” “怎么了?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵淹真,是天一觀的道長讶迁。 經(jīng)常有香客問我,道長核蘸,這世上最難降的妖魔是什么巍糯? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任啸驯,我火速辦了婚禮,結(jié)果婚禮上鳞贷,老公的妹妹穿的比我還像新娘坯汤。我一直安慰自己,他們只是感情好搀愧,可當我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著疆偿,像睡著了一般咱筛。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上杆故,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天迅箩,我揣著相機與錄音,去河邊找鬼处铛。 笑死饲趋,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的撤蟆。 我是一名探鬼主播奕塑,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼家肯!你這毒婦竟也來了龄砰?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤讨衣,失蹤者是張志新(化名)和其女友劉穎换棚,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體反镇,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡固蚤,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了歹茶。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片夕玩。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖辆亏,靈堂內(nèi)的尸體忽然破棺而出风秤,到底是詐尸還是另有隱情,我是刑警寧澤扮叨,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布缤弦,位于F島的核電站,受9級特大地震影響彻磁,放射性物質(zhì)發(fā)生泄漏碍沐。R本人自食惡果不足惜狸捅,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望累提。 院中可真熱鬧尘喝,春花似錦、人聲如沸斋陪。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽无虚。三九已至缔赠,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間友题,已是汗流浹背嗤堰。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留度宦,地道東北人踢匣。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像戈抄,于是被迫代替她去往敵國和親离唬。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,870評論 2 361