कक्षा 9–12Computationपाठ उपलब्ध
Algorithms, correctness and efficiency
Searching and sorting, proving algorithms correct with loop invariants, counting steps, and comparing growth rates such as logarithmic, linear and quadratic time.
math.comp.algorithms-and-efficiency
इस पर आधारित
15 अनिवार्य पूर्वापेक्षाएँ (बिल्कुल नीचे तक)
आप सीखेंगे
- Implement linear search, binary search and a simple sort, and trace them on examples.
- Prove an algorithm correct using a loop invariant, for example binary search or Euclid's algorithm.
- Count the steps of simple algorithms and compare growth rates n, n log n and n².
परिभाषा
- A loop invariant is a statement that holds before the first iteration of a loop and is preserved by every iteration.
- The running time of an algorithm is the number of basic steps it takes, as a function of the size of its input.
प्रमेय
- Binary search on a sorted list of n items uses at most ⌊log₂ n⌋ + 1 comparisons.
- Every comparison-based sorting algorithm needs at least log₂(n!) comparisons in the worst case, which grows like n log n.
- An algorithm is correct if, for every valid input, it terminates and produces the specified output.
आम भ्रांतियाँ
- Thinking that testing on a few inputs proves an algorithm correct.
- Believing faster computers make algorithmic efficiency irrelevant.
आगे ले जाता है
वैकल्पिक खोजें
- Computational complexity Some problems seem to require far more time than others; whether P equals NP is a famous open problem.
- ← Divisibility, Euclid's algorithm and unique factorisation
- ← Recurrences and generating functions
अधिगम पथ
आगे पढ़ने के लिए
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms