Big-O و بهینهسازی راهحل Brute Force
آمادگی مصاحبهٔ الگوریتمی با Python
- In 90 minutes, turn an input-output contract into a correct brute-force algorithm, clarifying size limits, duplicates, empty inputs, and permission to modify input.
- Use Python lists, strings, indexing, iteration, and half-open ranges; distinguish contiguous subarrays from subsequences.
- Analyze constant, logarithmic, linear, sorting, quadratic, and exponential growth; distinguish worst-case, expected, and amortized costs.
- Account for Python slicing, list membership, append, pop, sorting, and constant-time len on built-in lists; separate auxiliary space from output space.
- Develop Product of Array Except Self from repeated multiplication to prefix and suffix reuse, first choosing what work can be reused independently and then implementing the linear-time solution.
- Introduce loop invariants through initialization, preservation, and termination; justify the prefix and suffix products and explain why a full output generally requires inspecting every input value.
- Test empty inputs under the agreed contract, single elements, negative values, and zero counts; diagnose hidden copying and unsupported optimality claims.
قرارداد دقیق و مبنای Brute Force
**قرارداد مسئله**
برای هر موقعیت، حاصلضرب همهٔ عضوها بهجز عضو همان موقعیت؛ بدون تقسیم.
تکرار، منفی و صفر مجاز؛ ورودی بدون تغییر.
**مرزها و فرض تحلیل**
ورودی خالی: \([]\mapsto[]\)
حاصلضرب مجموعهٔ خالی: \(1\)؛ پس \([a]\mapsto[1]\).
فرض: هزینهٔ هر ضرب ثابت است؛ برای عددهای خیلی بزرگ Python، طول عددها هم مهم است.
**مثال، موقعیتبهموقعیت**
\(\mathrm{nums}=[2,3,4]\)
\(i=0:\quad 3\times4=12\)
\(i=1:\quad 2\times4=8\)
\(i=2:\quad 2\times3=6\)
\(\mathrm{out}=[12,8,6]\)
**راهحل مستقیم: Brute Force**
```python
def brute(nums):
n = len(nums)
out = []
for i in range(n):
p = 1
for j in range(n):
if j != i:
p *= nums[j]
out.append(p)
return out
```
**موقعیت و پیمایش**
انتهای range باز است:
\(\operatorname{range}(0,3)\longrightarrow 0,1,2\)
list و string: دسترسی با index؛ پیمایش مستقیم: عضوها بهترتیب.
**چه چیزی جستوجو نمیشود؟**
در \([2,3,4]\):
subarray پیوسته است: \([2,3]\)
subsequence با حذف عضو هم ساخته میشود: \([2,4]\)
اینجا هیچکدام را جستوجو نمیکنیم؛ برای هر موقعیت جواب میسازیم.
هزینهٔ واقعی، نه ظاهر حلقهها
**Big-O: رشد هزینه، نه ثانیه**
Brute Force: \(n\times n=n^2\Rightarrow O(n^2)\)؛ با ورودی \(2n\): \((2n)^2=4n^2\)
حلقههای تودرتو با داخلی ثابت: \(n\times3=3n\Rightarrow O(n)\)
دو پیمایش پشتسرهم: \(n+n=2n\Rightarrow O(n)\)
**نردبان رشد در اندازهٔ \(n=8\)**
ثابت: \(1\)؛ خطی: \(8\)؛ درجهدو: \(8^2=64\)؛ نمایی: \(2^8=256\)
نصفکردن: \(8\to4\to2\to1\)؛ \(\log_2 8=3\)
sorting: \(n\log_2 n=8\times3=24\)
مقایسهٔ رشد؛ نه شمارش دقیق دستورها
**هزینههای پنهان Python**
روی list داخلی: دسترسی با index و len: \(O(1)\)؛ عضویت با in: در بدترین حالت \(O(n)\)
slice با \(k\) عضو: زمان و حافظهٔ \(O(k)\)
چسباندن listها: کپی؛ slice معمولی string: معمولاً متن تازه
**append و pop**
append: هزینهٔ amortized برابر \(O(1)\)؛ گاهی کپی برای افزایش ظرفیت
pop از آخر: معمولاً \(O(1)\)
pop از اول: \(O(n)\)، بهدلیل جابهجایی عضوها
**نوع تضمین هزینه را مشخص کن**
amortized: هزینهٔ سرشکن روی دنبالهٔ عملیات، نه تضمین ثابت برای هر فراخوانی
worst-case: پرهزینهترین ورودی مجاز
expected: میانگین با فرض احتمالی روشن؛ نه حدس دربارهٔ ورودی معمولی
**in-place لزوماً حافظهٔ ثابت نیست**
sort در Python: تغییر همان list؛ زمان worst-case برابر \(O(n\log n)\)، auxiliary space برابر \(O(n)\)
sorted: علاوه بر حافظهٔ کاری، یک list خروجی تازه
حافظهٔ خروجی را جدا از auxiliary space گزارش کن.
دو پیمایش، بدون کار تکراری
برای هر موقعیت، فقط عضوهای قبل و بعد؛ بدون تقسیم و بدون تغییر در `nums`.
**دو بخش مستقل**
\[ \mathrm{out}[i]=\underbrace{\left(\prod_{j=0}^{i-1}\mathrm{nums}[j]\right)}_{\mathrm{prefix}}\;\underbrace{\left(\prod_{j=i+1}^{n-1}\mathrm{nums}[j]\right)}_{\mathrm{suffix}} \]
عضو فعلی در هیچکدام نیست.
**راه میانی: دو list جدا**
\[ L[i]=\prod_{j=0}^{i-1}\mathrm{nums}[j],\qquad R[i]=\prod_{j=i+1}^{n-1}\mathrm{nums}[j] \]
زمان \(O(n)\)، حافظهٔ کمکی \(O(n)\)؛ بهتر: نگهداری سمت چپ در خود خروجی.
**ساخت تابع و خروجی**
\[ \begin{array}{l}\texttt{def productexceptself(nums):}\\\quad\texttt{n = len(nums)}\\\quad\texttt{out = [1] * n}\\\quad\texttt{left = 1}\end{array} \]
**پیمایش اول: ذخیره، سپس گسترش**
\[ \begin{array}{l}\quad\texttt{for i in range(n):}\\\qquad\texttt{out[i] = left}\\\qquad\texttt{left *= nums[i]}\end{array} \]
خروجی فعلاً فقط حاصلضرب عضوهای قبل را نگه میدارد.
**آغاز پیمایش معکوس**
\[ \begin{array}{l}\quad\texttt{right = 1}\\\quad\texttt{for i in range(n - 1, -1, -1):}\end{array} \]
**پیمایش دوم: تکمیل، سپس گسترش**
\[ \begin{array}{l}\qquad\texttt{out[i] *= right}\\\qquad\texttt{right *= nums[i]}\end{array} \]
حاصلضرب سمت راست به حاصلضرب سمت چپ اضافه میشود؛ عضو فعلی هنوز وارد نشده است.
**بازگرداندن خروجی**
\[ \quad\texttt{return out} \]
بدون تقسیم؛ `nums` بدون تغییر. این روش به دو بخش مستقلِ قبل و بعد متکی است؛ sorting جایگزین آن نیست.
درستی دو پیمایش با loop invariant
ورودی: \(a=[2,3,4]\)؛ حاصلضرب خالی: \(1\)
**شروع پیمایش اول**
\[ \mathrm{out}=[1,1,1],\qquad \mathrm{left}=1 \]
**ذخیره، سپس بهروزرسانی**
\[ i=0:\quad \mathrm{out}[0]\gets1,\quad \mathrm{left}\gets1\cdot2=2 \]
\[ i=1:\quad \mathrm{out}[1]\gets2,\quad \mathrm{left}\gets2\cdot3=6 \]
\[ i=2:\quad \mathrm{out}[2]\gets6,\quad \mathrm{left}\gets6\cdot4=24\qquad\Rightarrow\quad\mathrm{out}=[1,2,6] \]
فعلاً فقط حاصلضرب سمت چپ؛ نه جواب نهایی.
**پیمایش برگشتی؛ تکمیل، سپس بهروزرسانی**
\[ \begin{aligned}\mathrm{right}&=1\\i=2:\quad\mathrm{out}[2]&\gets6\cdot1=6,\quad\mathrm{right}\gets1\cdot4=4\end{aligned} \]
\[ i=1:\quad\mathrm{out}[1]\gets2\cdot4=8,\quad\mathrm{right}\gets4\cdot3=12 \]
**جواب نهایی**
\[ \begin{aligned}i=0:\quad\mathrm{out}[0]&\gets1\cdot12=12,\quad\mathrm{right}\gets12\cdot2=24\\\mathrm{out}&=[12,8,6]\end{aligned} \]
**loop invariant پیمایش اول**
\[ \begin{aligned}\mathrm{left}&=\prod_{j=0}^{i-1}a[j]\\\forall k<i:\quad\mathrm{out}[k]&=\prod_{j=0}^{k-1}a[j]\\i=0:&\quad\prod_{j=0}^{-1}a[j]=1\\\mathrm{out}[i]&\gets\mathrm{left}\\\mathrm{left}&\gets\mathrm{left}\cdot a[i]=\prod_{j=0}^{i}a[j]\end{aligned} \]
قبل از هر دور. initialization: حاصلضرب خالی؛ preservation: ذخیره قبل از ورود عضو فعلی؛ termination: همهٔ خانهها حاصلضرب سمت چپ را دارند.
**loop invariant پیمایش برگشتی**
\[ \begin{aligned}\mathrm{right}&=\prod_{j=i+1}^{n-1}a[j]\\\mathrm{out}[i]&=\prod_{j=0}^{i-1}a[j]\\\forall k>i:\quad\mathrm{out}[k]&=\prod_{j\ne k}a[j]\\\mathrm{out}[i]&\gets\mathrm{out}[i]\cdot\mathrm{right}=\prod_{j\ne i}a[j]\\\mathrm{right}&\gets a[i]\cdot\mathrm{right}=\prod_{j=i}^{n-1}a[j]\end{aligned} \]
شروع: سمت راست آخرین عضو خالی است. حفظ: تکمیل جواب، سپس ورود عضو فعلی. پایان: همهٔ جوابها کاملاند.
**خطا: بهروزرسانی قبل از ذخیره**
\[ i=0:\quad\mathrm{left}\gets1\cdot2=2\quad\Rightarrow\quad\mathrm{out}[0]=2\ne1 \]
عضو فعلی نباید وارد حاصلضرب سمت چپ خودش شود. تست خطا پیدا میکند؛ invariant دلیل عمومی درستی را میدهد.
ردگیری مرزی و هزینهٔ واقعی
| حالت | ورودی | رفت: out و left | برگشت: out و right | خروجی | بررسی و هزینه |
| --- | --- | --- | --- | --- | --- |
| یک صفر | \([2,0,4]\) | \(\begin{aligned}out&=[1,2,0]\\left&:2\to0\to0\end{aligned}\) | \(\begin{aligned}right&=1\\i=2:&\ out=[1,2,0],\ right=4\\i=1:&\ out=[1,8,0],\ right=0\\i=0:&\ out=[0,8,0],\ right=0\end{aligned}\) | \([0,8,0]\) | |
| دو صفر | \([0,3,0]\) | \(\begin{aligned}out&=[1,0,0]\\left&:0\to0\to0\end{aligned}\) | \(\begin{aligned}right&=1\\i=2:&\ out=[1,0,0],\ right=0\\i=1:&\ out=[1,0,0],\ right=0\\i=0:&\ out=[0,0,0],\ right=0\end{aligned}\) | \([0,0,0]\) | بدون شاخهٔ ویژه برای صفر |
| تکعضوی | \([-2]\) | \(out=[1],\ left=-2\) | \(\begin{aligned}right&=1\\out[0]&=1\times1=1\\right&=1\times(-2)=-2\end{aligned}\) | \([1]\) | |
| خالی | \([]\) | range خالی | range خالی | \([]\) | |
| تمرین: منفی | \([-2,3]\) | | | \([3,-2]\) | مقایسه با brute؛ nums بدون تغییر |
| تمرین: تکراری | \([2,2]\) | | | \([2,2]\) | مقایسه با brute؛ nums بدون تغییر |
| brute | | | | | زمان: \(O(n^2)\)؛ حافظهٔ خروجی: \(O(n)\) |
| دو پیمایش | خروجی کامل؛ ورودی عمومی | \(O(n)+O(n)+O(n)=O(n)\) | هشدار: slice در حلقه ← کپی؛ احتمال \(O(n^2)\) | \(\Omega(n)\Rightarrow\Theta(n)\) | خروجی: \(O(n)\)؛ auxiliary space: \(O(1)\) |
بازگشت به دوره