Hyppää sisältöön

Ei vielä käännetty

Tätä sivua ei ole vielä käännetty suomeksi, joten se näytetään englanniksi. Auta kääntämään

Range Operations Complexity

The range type is an immutable sequence of numbers used for iteration. It generates values lazily without storing all numbers in memory.

Complexity Reference

Operation Time Space Notes
range(stop) O(1) O(1) Create range object
range(start, stop) O(1) O(1) Create range object
range(start, stop, step) O(1) O(1) Create range object
len() O(1) O(1) Calculated, not stored
access[i] O(1) O(1) Direct calculation
in (membership) O(1)* O(1) *Arithmetic check for int/bool; other types fall back to an O(n) scan
index(value) O(1)* O(1) *Solves an equation for int/bool; other types scan in O(n)
count(value) O(1)* O(1) *Single check for int/bool; other types scan in O(n)
iteration O(n) O(1) n = number of items; yields on demand
reversed() O(1) O(1) Iterator, not materialized
list(range(...)) O(n) O(n) Convert to list

Implementation Details

Lazy Evaluation

# Range is lazy - no values stored
r = range(1000000)  # O(1) - very fast

# Size is O(1)
len(r)              # O(1) - calculated

# Iteration is still O(n) for each item
for i in r:         # O(n) total
    print(i)

Efficient Membership Testing

# Membership check is O(1) - solves equation
r = range(10, 100, 5)
50 in r             # O(1) - True (10 + 5*k = 50)
51 in r             # O(1) - False (no integer k works)

# Much faster than list
lst = list(range(10, 100, 5))
50 in lst           # O(n) - linear search

Direct Access

# Access any element in O(1)
r = range(1000000)
r[500000]           # O(1) - calculated: start + step*index

# Using formula: value = start + step * index
r = range(10, 100, 5)
r[0]                # 10
r[5]                # 35 (10 + 5*5)
r[10]               # 60 (10 + 5*10)

Common Use Cases

Iteration

# Efficient iteration
for i in range(1000000):  # O(n) iteration, O(1) per item
    process(i)

# More efficient than
for i in list(range(1000000)):  # Uses O(n) memory
    process(i)

Loop Counting

# Standard range for loops - O(1) to create, O(n) to iterate, O(1) space
for i in range(10):
    print(i)  # 0 to 9

# With start and step - same cost; step does not change it
for i in range(10, 100, 5):
    print(i)  # 10, 15, 20, ..., 95

# Reverse iteration - no list is built, so still O(1) space
for i in range(100, 10, -5):
    print(i)  # 100, 95, 90, ..., 15

Indexing

# Works with enumerate - O(n) total, O(1) space
for idx, val in enumerate(items):
    print(idx, val)

# Or explicit range - O(1) for len() and range(); items[i] is O(1) for a
# list or tuple, but not for every sequence
for i in range(len(items)):
    print(i, items[i])
# Same O(n) total; enumerate avoids one index lookup per item, and works on
# sequences that index in worse than constant time

Performance Characteristics

Range vs List

import sys

# Range: O(1) memory
r = range(1000000)
print(sys.getsizeof(r))  # ~48 bytes - fixed size!

# List: O(n) memory
lst = list(range(1000000))
print(sys.getsizeof(lst))  # ~8MB+ - proportional to size

Membership Testing

# Range: O(1)
r = range(10000000)
9999999 in r  # O(1) - instant

# List: O(n)
lst = list(range(10000000))
9999999 in lst  # O(n) - might take milliseconds

Iteration

# Both O(n) for full iteration
r = range(1000000)
for i in r:  # O(1) per item, O(n) total
    pass

# But range doesn't use O(n) memory
lst = list(range(1000000))
for i in lst:  # O(1) per item, O(n) total, but O(n) memory
    pass

Edge Cases

Empty Range

r = range(0)     # O(1) - Empty
len(r)           # O(1) - 0, computed from start/stop/step
list(r)          # O(1) here - []

r = range(5, 5)  # Empty
len(r)           # O(1) - 0

r = range(10, 5)  # Empty (reversed with positive step)
len(r)           # O(1) - 0, no scan needed to discover emptiness

Negative Steps

r = range(10, 0, -1)  # O(1) - a negative step costs no more to create
list(r)          # O(n) - [10, 9, 8, ..., 1], materializes every value

r = range(10, 0, -2)  # O(1)
list(r)          # O(n) - [10, 8, 6, 4, 2], n = len(r), not the span

Large Ranges

# Safe - never materializes all values
r = range(10**18)  # Huge range, still O(1) memory
len(r)             # 10^18
r[0]               # 0
r[999999999999999] # 999999999999999

Version Notes

  • All Python 3.x: Core complexity unchanged
  • Python 2.x: Had xrange for lazy evaluation (now built-in)
  • List - For materialized sequences
  • Iteration - For looping
  • Enumerate - For indexed iteration