Python
समस्या-समाधान · #9 / 11

Complexity + Memory Model

Big-O, mutability, और copying

यह क्यों मायने रखता है

गति और स्थान ही वे चीज़ें हैं जो स्वीकृत समाधान को TLE समाधान से अलग करती हैं।

मूल विचार

प्रति input आकार operations में सोचिए। list.append() O(1) amortised है; list.insert(0, x) O(n) है क्योंकि सब कुछ खिसकता है। set / dict lookup O(1) है; list membership (x in lst) O(n) है।

O(n²) को काम करते देखिए

Bubble sort हर सटे हुए जोड़े की तुलना करता है और हर पास में सबसे बड़े को अंत तक उछाल देता है। Auto दबाइए और गिनिए: 24 तत्वों में ~200 तुलनाएँ लगती हैं। इसे दोगुना करके 48 करने पर 2× नहीं — ~4× लगेगा। O(n²) ऐसा ही दिखता है।

comparisons: 0 swaps: 0

आज़माकर देखिए

list और set membership के बीच का अंतर मापिए:

import time

N = 50000
data = list(range(N))
data_set = set(data)
needles = [N - 1, N // 2, 0]

t0 = time.perf_counter()
hits_list = sum(1 for x in needles if x in data)
t1 = time.perf_counter()
hits_set = sum(1 for x in needles if x in data_set)
t2 = time.perf_counter()

print(f"list lookups: {hits_list}  time: {(t1-t0)*1e6:.1f} µs")
print(f"set  lookups: {hits_set}  time: {(t2-t1)*1e6:.1f} µs")
not loaded

Shallow बनाम deep copy — mutables लोगों को चौंकाते हैं:

import copy

grid = [[0] * 3 for _ in range(3)]
shallow = list(grid)       # same inner lists!
deep = copy.deepcopy(grid)

shallow[0][0] = 99
deep[0][0] = -1

print("grid    :", grid)
print("shallow :", shallow)
print("deep    :", deep)
not loaded

जगह पर बदलाव बनाम नया object:

# sorted() makes a new list, sort() mutates in place
nums = [3, 1, 4, 1, 5]
asc = sorted(nums)         # new
nums.sort(reverse=True)    # in place
print("asc :", asc)
print("nums:", nums)
not loaded

झटपट जाँच

छोटे अभ्यास

आम ग़लतियाँ

मुख्य बातें