Algorithms complexity / Growth of Functions
渐进记号
Asymptotic Notation
A way to describe the rate with which the running time of the algorithm increases compared to the rate at which the size of the problem () increases.
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fed7e9034-53d9-450b-a95d-770bb451aefd%2FUntitled.png?table=block&id=fe6fd651-2c08-4bec-93c6-bb127292de7c&t=fe6fd651-2c08-4bec-93c6-bb127292de7c&width=288&cache=v2)
o-notation
- 的增长率小于
- 明确(准确计算)知道小于它
- For example, , but
O-notation
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F8f9712bc-4950-4ed0-bb9b-fb96932ec237%2FUntitled.png?table=block&id=3900c48b-0b21-4a73-8047-f9bd45eda489&t=3900c48b-0b21-4a73-8047-f9bd45eda489&width=192&cache=v2)
when we have only an asymptotic upper bound
💡 Always concerned with worst case(max) time requirement
的增长率小于等于
- 不确定是否等于时使用(近似复杂度)
Θ-notation
Ω-notation
![notion image](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2F00c8654a-8360-413f-9b7e-a6bf32b7b299%2FUntitled.png?table=block&id=6b53ff0c-da1b-43da-ac98-0462b20031f6&t=6b53ff0c-da1b-43da-ac98-0462b20031f6&width=192&cache=v2)
when we have only an asymptotic lower bound
的增长率大于等于
ω-notation
- 的增长率大于