TreeviewCopyright © aleen42 all right reserved, powered by aleen42

How to analyse an algorithm Back

1. Overview

Main thoughts of designing algorithms:

Sometimes, the performance of an algorithm matters so much, when the size of a problem n is so big.

It is not always true for high performance, when an algorithm depends on what is more important like the following items:

  • modularity(模塊性)
  • correctness(正確性)
  • maintainability(可維護性)
  • functionality(功能性)
  • robustness(健壯性)
  • user-friendliness(用戶友好性)
  • programmer time(編程效率)
  • simplicity(簡潔度)
  • extensibility(可擴展性)
  • reliability(可靠度)

There are three kinds of analysis:

  • Worst-case(考慮該類問題的最優解, 關注最壞情況下的最好情況)
  • Average-case
  • Best-case(虛假的)

There are three notations of time

  • θ (drop low-order terms, and ignore leading constants)

  • Ω

  • O

2. Recursive Algorithm

  • Substitution: 猜想 (通常通過畫Recursive Tree來給出猜想) 並證明

    • guess
    • verify

    • solve

  • Recursive Tree: 通過畫出遞歸樹來求解開銷

  • Master:

Empty Comments
Sign in GitHub

As the plugin is integrated with a code management system like GitLab or GitHub, you may have to auth with your account before leaving comments around this article.

Notice: This plugin has used Cookie to store your token with an expiration.