尋找演算法時間複雜度的簡單方法

對於剛開始解決問題的初學者來說，時間複雜度被認為是最困難的主題之一。在這裡，我提供時間複雜度分析備忘錄。我希望這有幫助。如果您有任何疑問，請告訴我。

時間複雜度分析備忘錄

快速參考表

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中文網其他相關文章！