iT邦幫忙

0

【演算法】L2 演算法複雜性與問題下界

  • 分享至 

  • xImage
  •  

L2 演算法複雜性與問題下界

漸進符號

  • f(n) = O(g(n)):最多
    • |f(n)| <= c|g(n)|
  • f(n) = Ω(g(n)):最少
    • |f(n)| >= c|g(n)|
  • f(n) = Θ(g(n))
    • c1|g(n)| <= |f(n)| <= c2|g(n)|

比較

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

演算法比較

Straight Insertion Sort

  • best case:O(n)
  • worst case:O(n^2)
  • average case:O(n^2)

Binary Search

  • best case:O(1)
  • worst case:O(log n)
  • average case:O(log n)

Selection Sort

  • best case:O(n)
  • worst case:O(n^2)
  • average case:O(nlog n)

Quick Sort

  • best case:O(nlog n)
  • worst case:O(n^2)
  • average case:O(nlog n)

圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言