アルゴリズムの時間計算量を見つける簡単な方法

時間計算量は、問題解決を始めたばかりの初心者にとって最も難しいトピックの 1 つと考えられています。ここでは、時間計算量解析のチートシートを提供します。これがお役に立てば幸いです。ご質問がございましたら、お知らせください。

時間計算量分析のチートシート

早見表

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 中国語 Web サイトの他の関連記事を参照してください。