حالت آفلاین — محتوا از حافظهٔ کش نمایش داده می‌شود
آموزش الگوریتم و حل مسئله با پایتون؛ تمرین عملی

رفع خطای شمارش زوج‌ها و رشد O(n²) در پایتون

تحلیل الگوریتم در پایتون؛ از قرارداد تا شمارش عملیات · 0٪

✍️ وقتی هر عضو را با اعضای بعد از خودش مقایسه می‌کنیم، یک حلقه کافی نیست. برای چهار عضو، عضو اول سه همتا دارد، عضو دوم دو همتا و عضو سوم یک همتا؛ جمعاً شش زوج می‌سازیم. زوج شامل دو جای متفاوت است و ترتیب جای‌ها مهم نیست، پس (0, 2) و (2, 0) یک زوج هستند.

برای نمونه، فهرست سه‌عضوی ['a', 'b', 'c'] فقط زوج‌های شماره خانه [0, 1]، [0, 2] و [1, 2] را دارد. حتی اگر مقدارهای دو خانه یکسان باشند، خود خانه‌ها همچنان متفاوت‌اند. کد اولیه، هر دو جهت و حتی مقایسه هر عضو با خودش را می‌شمارد؛ همین باعث نتیجه بزرگ‌تر می‌شود.

حلقه داخلی را طوری اصلاح کن که فقط خانه‌های بعد از i را ببیند. تعداد درست n * (n - 1) // 2 است، ولی برای دیدن مسیر کار از حلقه استفاده کن. رشد این تعداد درجه دوم یا O(n²) است. خطای رایج اینه که حلقه داخلی را از خود i شروع کنیم؛ در آن صورت زوج‌های خودی هنوز باقی می‌مانند و تک‌عضوی به اشتباه یک می‌شود.

تابع آماده course_check فقط برای ارزیابی است: تابع اصلی را صدا می‌زند و حفظ ورودی را بررسی می‌کند. آن را تغییر نده؛ پاسخ تو همان تابع خواسته‌شده است.

فعالیت شما

تابع count_pairs(nums) فهرست عددهای صحیح را می‌گیرد و تعداد زوج‌های شاخص i < j را برمی‌گرداند؛ مقدار اعضا در شمارش نقشی ندارد و ورودی تغییر نمی‌کند. برای خالی و تک‌عضوی جواب 0 و برای [5,5,9] جواب 3 است. تابع آماده course_check فقط برای ارزیابی است: تابع اصلی را صدا می‌زند و حفظ ورودی را بررسی می‌کند. آن را تغییر نده؛ پاسخ تو همان تابع خواسته‌شده است.

مطالعهٔ این گام برای همه آزاد است

برای پاسخ‌دادن، بررسی پاسخ، ثبت پیشرفت و استفاده از دستیار باید شرایط شرکت در فعالیت‌ها را داشته باشید.

برای انجام فعالیت وارد شوید

برای انجام فعالیت‌ها ابتدا این دوره‌های پیش‌نیاز را تکمیل کنید:

کد اولیهٔ فعالیت

def count_pairs(nums):
    count = 0
    for i in range(len(nums)):
        for j in range(len(nums)):
            count += 1
    return count

# این تابع آماده فقط برای ارزیابی است؛ آن را تغییر نده.
def course_check(*args):
    from copy import deepcopy
    before = deepcopy(args)
    result = count_pairs(*args)
    if args != before:
        raise ValueError('ورودی نباید تغییر کند.')
    return result