查找算法时间复杂度的简单方法

对于刚开始解决问题的初学者来说，时间复杂度被认为是最困难的主题之一。在这里，我提供时间复杂度分析备忘单。我希望这有帮助。如果您有任何疑问，请告诉我。

时间复杂度分析备忘单

快速参考表

O(1)       - Constant time
O(log n)   - Logarithmic (halving/doubling)
O(n)       - Linear (single loop)
O(n log n) - Linearithmic (efficient sorting)
O(n²)      - Quadratic (nested loops)
O(2ⁿ)      - Exponential (recursive doubling)
O(n!)      - Factorial (permutations)

识别模式

1. O(1) - 常数

# Look for:
- Direct array access
- Basic math operations
- Fixed loops
- Hash table lookups

# Examples:
arr[0]
x + y
for i in range(5)
hashmap[key]

2. O(log n) - 对数

# Look for:
- Halving/Doubling
- Binary search patterns
- Tree traversal by level

# Examples:
while n > 0:
    n = n // 2

left, right = 0, len(arr)-1
while left <= right:
    mid = (left + right) // 2

3. O(n) - 线性

# Look for:
- Single loops
- Array traversal
- Linear search
- Hash table building

# Examples:
for num in nums:
    # O(1) operation
    total += num

for i in range(n):
    # O(1) operation
    arr[i] = i

4. O(n log n) - 线性

# Look for:
- Efficient sorting
- Divide and conquer
- Tree operations with traversal

# Examples:
nums.sort()
sorted(nums)
merge_sort(nums)

5. O(n²) - 二次

# Look for:
- Nested loops
- Simple sorting
- Matrix traversal
- Comparing all pairs

# Examples:
for i in range(n):
    for j in range(n):
        # O(1) operation

# Pattern finding
for i in range(n):
    for j in range(i+1, n):
        # Compare pairs

6. O(2ⁿ) - 指数

# Look for:
- Double recursion
- Power set
- Fibonacci recursive
- All subsets

# Examples:
def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

def subsets(nums):
    if not nums: return [[]]
    result = subsets(nums[1:])
    return result + [nums[0:1] + r for r in result]

常见操作时间复杂度

数组/列表操作

# O(1)
arr[i]              # Access
arr.append(x)       # Add end
arr.pop()           # Remove end

# O(n)
arr.insert(i, x)    # Insert middle
arr.remove(x)       # Remove by value
arr.index(x)        # Find index
min(arr), max(arr)  # Find min/max

字典/集合操作

# O(1) average
d[key]              # Access
d[key] = value      # Insert
key in d            # Check existence
d.get(key)          # Get value

# O(n)
len(d)              # Size
d.keys()            # Get keys
d.values()          # Get values

字符串操作

# O(n)
s + t               # Concatenation
s.find(t)           # Substring search
s.replace(old, new) # Replace
''.join(list)       # Join

# O(n²) potential
s += char           # Repeated concatenation

循环分析

单循环

# O(n)
for i in range(n):
    # O(1) operations

# O(n/2) = O(n)
for i in range(0, n, 2):
    # Skip elements still O(n)

嵌套循环

# O(n²)
for i in range(n):
    for j in range(n):
        # O(1) operations

# O(n * m)
for i in range(n):
    for j in range(m):
        # Different sizes

# O(n²/2) = O(n²)
for i in range(n):
    for j in range(i, n):
        # Triangular still O(n²)

多重循环

# O(n + m)
for i in range(n):
    # O(1)
for j in range(m):
    # O(1)

# O(n + n²) = O(n²)
for i in range(n):
    # O(1)
for i in range(n):
    for j in range(n):
        # O(1)

递归分析

线性递归

# O(n)
def factorial(n):
    if n <= 1: return 1
    return n * factorial(n-1)

二元递归

# O(2ⁿ)
def fibonacci(n):
    if n <= 1: return n
    return fibonacci(n-1) + fibonacci(n-2)

分而治之

# O(n log n)
def mergeSort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left = mergeSort(arr[:mid])
    right = mergeSort(arr[mid:])
    return merge(left, right)

优化危险信号

隐藏循环

# String operations
for c in string:
    newStr += c  # O(n²)

# List comprehension
[x for x in range(n) for y in range(n)]  # O(n²)

内置功能

len()           # O(1)
min(), max()    # O(n)
sorted()        # O(n log n)
list.index()    # O(n)

分析技巧

1. 计算嵌套循环
2. 检查递归分支
3. 考虑隐藏操作
4. 寻找分而治之
5. 检查内置函数复杂性
6. 考虑平均情况与最坏情况
7. 监视循环变量
8. 考虑输入约束

感谢您的阅读，如果您觉得这篇文章对您有帮助，请点赞。干杯！

以上是查找算法时间复杂度的简单方法的详细内容。更多信息请关注PHP中文网其他相关文章！