رفتن به نوشته‌ها

مسئله حاصل‌ضرب اعداد

چند روز پیش با یکی از دوستانم صحبت می‌کردم که توی یک جلسه مصاحبه یک سوال جالب ازش پرسیده شده بود. از سوال خوشم اومد و می‌خوام توی یک پست در موردش بنویسم. تصور کنید که یک آرایه داریم تشکیل شده از اعداد به طول N و قرار هست الگوریتمی طراحی کنیم که از روی این آرایه یک آرایه جدید تولید کنه به طوری که به جای هر عدد حاصل‌ضرب بقیه عناصر آرایه قرار بگیره.
مثلا اگر آرایه ورودی [۵, ۳, ۲] بود آرایه خروجی به جای ۲ مقدار ۳×۵ ، به جای ۳ مقدار ۲×۵ و به جای ۵ مقدار ۲×۳ قرار بده.

اولین تلاش، O(n2)

احتمالا اولین جوابی که به ذهن هر برنامه‌نویسی می‌رسه همچین چیزیه:

def solve(input):
    output = []
    for i in range(0, len(input)):
        res = 1
        for j in range(0, len(input)):
            if j != i:
                res *= input[j]
        output.append(res)
    return output

اما تحلیل این الگوریتم نتیجه چندان جالبی نمیده، اگر عمل اصلی این الگوریتم رو ضرب درنظر بگیریم تعداد دفعات تکرارش بر حسب N میشه، حلقه بیرونی N بار اجرا میشه و حلقه داخلی N-1 بار پس تعداد دفعات عمل ضرب میشهN*(N-1) یعنی  N2-N که یعنی O(N2)

 

تلاش دوم، O(n) اما…

اگر ما یک‌بار حاصل ضرب کل عناصر رو بدست بیاریم و دفعات بعدی به هر عنصر که رسیدیم با استفاده از تقسیم اون عنصر رو از حاصل ضرب بیرون بکشیم چی؟یعنی همچین چیزی:

def solve2(input):
    all = 1
    for i in input:
        all *= i
    output = []
    for i in input:
        output.append(all / i)
    return output

اگر عمل اصلی رو ضرب یا حتی تقسیم در نظر بگیریم تعداد دفعات اجرا دقیقا میشه N و نتیجه تحلیل هم میشه O(n) اما یه مشکلی داره این الگوریتم، مشکلش هم اینه که خیلی به قول خارجی‌ها specific هستش!
فرض کنید می‌خوایم این مسئله رو تعمیم بدیم، به جای اینکه مثلا همیشه عملگر مورد نظر ضرب باشه، عملگر رو بذاریم تابعی مثل f یعنی ورودی اگر بود [a, b, c] خروجی باید باشه   [f(b,c), f(a,c), f(a,b)] .
در این صورت چون نمی‌تونیم در مورد تابع f فرض خاصی بکنیم نمی‌تونیم تابعی مثل g رو هم فرض کنیم که نقش عملگر تقسیم رو برامون بازی کنه و از توی f(a, b, c) مثلا a رو بیرون بکشه تا f(b, c) رو بدست بیاریم.

 

تلاش سوم، Dynamic Programming

اگر با دقت اولین تلاش رو بررسی کنیم متوجه میشیم که ما بار‌ها و بارها حاصل‌ضرب‌های تکراری رو حساب کردیم، اگر به نحوی بتونیم نتیجه این عملیات‌ها رو نگه داریم و بعدا استفاده کنیم شاید بتونیم از O(N2) به order بهتری برسیم.

ادامه دارد…

منتشر شده در دسته‌بندی نشده