jimmy 發問時間: 電腦與網際網路程式設計 · 9 年前

搜尋時間複雜度的問題

sequential search和binary search 的 best case和worst case分別為多少?

1 個解答

評分
  • 其威
    Lv 7
    9 年前
    最佳解答

    Time Complexity:

     - sequencial search:

      - best case: O(1)

      - worst case: O(n)

     - binary search:

      - best case: O(1)

      - worst case: O(log n)

    這裡的 n 指的是比較次數.

    如果你的每個 element 的比較動作不是 O(1), 則要再乘上比較動作的複雜度.

    如果你的容器不是 random accessible container, 則 binary search 要多乘上搜尋中間點的複雜度.

    Space Complexity:

     - sequencial search:

      - best case: O(1)

      - worst case: O(1)

     - binary search:

      - best case: O(1)

      - worst case: O(1)

還有問題?馬上發問,尋求解答。