GeezerVison

The World Wide Web, restored to 800 pixels of glory.

GeezerVison is showing python.github.io — پیچیدگی زمانی عملیات‌ها روی انواع توکار

پیچیدگی زمانی عملیات‌ها روی انواع توکار¶

این صفحه پیچیدگی زمانی عملیات‌های مختلف روی انواع توکار در سی‌پایتون را مستند می‌کند. پیاده‌سازی‌های دیگر پایتون ممکن است ویژگی‌های عملکردی متفاوتی داشته باشند. علاوه بر این، هزینه‌های لیست‌شده انواع توکار دقیق را فرض می‌کنند، زیرا نمونه‌های زیرکلاس‌ها ممکن است هزینه‌های متفاوتی داشته باشند.

ما از Big O notation برای توصیف نحوه رشد زمان اجرای یک عملیات با اندازه ورودی‌های آن استفاده می‌کنیم. مگر اینکه خلاف آن ذکر شده باشد، n تعداد المان‌های فعلی در ظرف را نشان می‌دهد، و k مقدار یک پارامتر عددی است، مانند یک اندیس یا تعداد تکرار.

`list`¶

فهرست‌ها دنباله‌های تغییرپذیر هستند؛ برای جزئیات بیشتر در مورد پیاده‌سازی به فهرست‌ها در CPython چگونه پیاده‌سازی شده‌اند؟ مراجعه کنید. بزرگترین هزینه‌ها ناشی از رشد فراتر از اندازه تخصیص فعلی است (چون همه چیز باید جابجا شود)، یا از درج یا حذف در جایی نزدیک به ابتدا (چون همه چیز بعد از آن باید جابجا شود). اگر نیاز به اضافه یا حذف در هر دو طرف دارید، به جای آن از collections.deque استفاده کنید.

عملیات	پیچیدگی
کپی (`l.copy()`)	O(n)
افزودن (`l.append(x)`) [1]	O(1)
حذف (`l.pop(k)`) [1] [2]	O(n - k)
درج (`l.insert(k, x)`) [1] [2]	O(n - k)
دریافت آیتم (`l[k]`)	O(1)
تنظیم آیتم (`l[k] = x`)	O(1)
حذف آیتم (`del l[k]`) [2]	O(n - k)
پیمایش	O(n)
دریافت اسلایس (`l[i:j]`)	O(j - i)
تنظیم اسلایس (`l[i:j] = t`) [1]	O(j - i) اگر len(t) == j - i، در غیر این صورت O(n - i + len(t))
حذف اسلایس (`del l[i:j]`)	O(n - i)
گسترش (`l.extend(t)`) [1] [3]	O(len(t))
مرتب‌سازی (`l.sort()`) [4]	O(n log n)
الحاق (`l1 + l2`)	O(len(l1) + len(l2))
ضرب (`l * k`)	O(nk)
`x in l`	O(n)
`min(l)`, `max(l)`	O(n)
بدست آوردن طول (`len(l)`) [5]	O(1)

`tuple`¶

یک tuple یک تغییرناپذیر دنباله است. از آنجا که یک تاپل هرگز تغییر نمی‌کند، هزینه‌ی درج یا حذف وجود ندارد، و ایجاد یک کپی صرفاً همان شیء را بازمی‌گرداند، بنابراین زمان ثابت است (O(1)).

عملیات	پیچیدگی
کپی (`tuple(t)`)	O(1)
دریافت آیتم (`t[k]`)	O(1)
دریافت اسلایس (`t[i:j]`)	O(j - i)
الحاق (`t1 + t2`)	O(len(t1) + len(t2))
ضرب (`t * k`)	O(nk)
پیمایش	O(n)
`x in t`	O(n)
`min(t)`, `max(t)`	O(n)
دریافت طول (`len(t)`) [5]	O(1)

`dict`, `frozendict`¶

زمان‌های فهرست‌شده برای شیء‌ها dict زمان‌های حالت‌میانگین هستند، زیرا آن‌ها فرض می‌کنند که تابع هش برای شیء‌ها به‌قدر کافی قوی است تا تصادفات را کم کند. آن‌ها همچنین فرض می‌کنند که کلیدها در میان مجموعه‌ی کلیدهای ممکن به‌خوبی توزیع شده‌اند. در بدترین حالت، وقتی هر کلید به یک مقدار هش می‌شود، هر یک از عملیات‌های O(1) در زیر در عوض زمان O(n) می‌طلبد. آن‌ها همچنین فرض می‌کنند که هش کردن و مقایسه یک کلید O(1) است. برای جزئیات بیشتر در مورد پیاده‌سازی، به دیکشنری‌ها در CPython چگونه پیاده‌سازی شده‌اند؟ مراجعه کنید.

یک frozendict تغییرناپذیر است، بنابراین تنظیم، حذف یا به‌روزرسانی آیتم‌ها را پشتیبانی نمی‌کند. سایر عملیات زیر با همان هزینه‌ها روی آن اعمال می‌شوند.

عملیات	پیچیدگی
`key in d`	O(1)
کپی (`d.copy()`) [6] [7]	O(n)
دریافت آیتم (`d[key]`, `d.get(key)`)	O(1)
تنظیم آیتم (`d[key] = value`) [1]	O(1)
حذف آیتم (`del d[key]`, `d.pop(key)`)	O(1)
به‌روزرسانی (`d.update(t)`, `d \|= t`) [1] [3] [7]	O(len(t))
پیمایش [7]	O(n)
دریافت طول (`len(d)`) [5]	O(1)

`set`, `frozenset`¶

از dict ببینید زیرا پیاده‌سازی‌های set و frozenset مشابه هستند، و همان احتیاط‌ها اعمال می‌شوند. در بدترین حالت، عملیات‌های O(1) به جای آن زمان O(n) می‌برند، و عملیات‌هایی که به جستجوی هر المان می‌پردازند به‌طوری مشابه کاهش می‌یابند.

یک frozenset تغییرناپذیر است، بنابراین از افزودن، حذف، یا عملیات‌های به‌روزرسانی درجا پشتیبانی نمی‌کند. موارد دیگر در پایین با همان هزینه‌ها بر آن اعمال می‌شوند.

عملیات	پیچیدگی
`x in s`	O(1)
کپی (`s.copy()`) [6] [7]	O(n)
افزودن (`s.add(x)`) [1]	O(1)
حذف (`s.discard(x)`, `s.remove(x)`)	O(1)
اتحاد (`s1 \| s2`, `s1.union(s2)`) [7]	O(len(s1) + len(s2))
به‌روزرسانی (`s1 \|= s2`, `s1.update(s2)`) [1] [7]	O(len(s2))
تقاطع (`s1 & s2`, `s1.intersection(s2)`) [7] [8]	O(min(len(s1), len(s2)))
به‌روزرسانی تقاطع (`s1 &= s2`, `s1.intersection_update(s2)`) [1] [7] [8]	O(min(len(s1), len(s2)))
تفاضل (`s1 - s2`, `s1.difference(s2)`) [7] [9]	O(len(s1))
به‌روزرسانی تفاضل (`s1 -= s2`, `s1.difference_update(s2)`) [1] [7] [8]	O(min(len(s1), len(s2)))
تفاضل متقارن (`s1 ^ s2`, `s1.symmetric_difference(s2)`) [7]	O(len(s1) + len(s2))
به‌روزرسانی تفاضل متقارن (`s1 ^= s2`, `s1.symmetric_difference_update(s2)`) [1] [7]	O(len(s2))
دریافت طول (`len(s)`) [5]	O(1)

`str`, `bytes`, `bytearray`¶

str و bytes به‌ترتیب دنباله‌های تغییرناپذیری از نویسه‌ها و بایت‌ها هستند. مانند تاپل‌ها، کپی کردن یکی از آن‌ها همان شیء اصلی را برمی‌گرداند. bytearray تغییرپذیر است و علاوه بر این، عملیات تغییر‌دهنده‌ی list (به‌جز sort()) را با همان هزینه‌ها پشتیبانی می‌کند. بااین‌حال، حذف از ابتدای آن با del (del b[0]، del b[:k]) فقط ابتدای بافر را جلو می‌برد، به‌جای اینکه بایت‌های باقی‌مانده را جابه‌جا کند، و پیچیدگی آن به‌طور سرشکن O(1) است.

عملیات	پیچیدگی
دریافت آیتم (`s[k]`)	O(1)
دریافت اسلایس (`s[i:j]`)	O(j - i)
الحاق (`s + t`) [10]	O\ (len(s) + len(t))
ضرب (`s * k`)	O(nk)
جستجوی زیررشته (`x in s`، `s.find(x)`، `s.index(x)`) [11]	O(n)
جستجوی معکوس زیررشته (`s.rfind(x)`، `s.rindex(x)`) [11] [12]	O\ (n × len(x))
کدگذاری یا کدگشایی [13]	O(n)
پیمایش	O(n)
دریافت طول (`len(s)`) [5]	O(1)

`memoryview`¶

شیء‌های memoryview به کد پایتون اجازه می‌دهند تا به داده‌های درونی یک شیء که از پروتکل بافر پشتیبانی می‌کند، بدون کپی کردن دسترسی پیدا کنند. به‌ویژه، برش یک نمای حافظه یک نما جدید بر روی همان بافر را برمی‌گرداند.

عملیات	پیچیدگی
ساخت (`memoryview(obj)`)	O(1)
دریافت آیتم (`v[k]`)	O(1)
دریافت اسلایس (`v[i:j]`)	O(1)
اندیس (`v.index(x)`) [11] [14]	O(n)
شمارش (`v.count(x)`) [14]	O(n)
تبدیل به بایت‌ها (`v.tobytes()`, `bytes(v)`)	O(n)
دریافت طول (`len(v)`) [5]	O(1)

`range`¶

یک شیء range آیتم‌های خود را به‌صورت تقاضا‌محور از مقادیر start، stop و step محاسبه می‌کند، بنابراین اکثر عملیات به طول محدوده وابسته نیستند.

عملیات	پیچیدگی
دریافت آیتم (`r[k]`)	O(1)
دریافت اسلایس (`r[i:j]`)	O(1)
`x in r` [15]	O(1)
اندیس و شمارش (`r.index(x)`، `r.count(x)`) [15]	O(1)
پیمایش	O(n)
`min(r)`، `max(r)`	O(n)
دریافت طول (`len(r)`) [5]	O(1)

یادداشت‌ها¶

[2] (1,2,3)

حذف یا پاپ کردن المان در اندیس k از یک فهرست با اندازه n باعث می‌شود تمام المان‌های بعد از k یک جایگاه به چپ جابجا شوند، که n - k - ۱ المان را جابجا می‌کند؛ درج در اندیس k المان‌های از k به بعد را یک جایگاه به راست جابجا می‌کند، که n - k المان را جابجا می‌کند. بدترین حالت اندیس ۰ است، جایی که کل بقیه‌ی فهرست باید جابجا شود؛ حالت میانگین، یک اندیس در میان فهرست، O(n/2) = O(n) عملیات را می‌گیرد؛ و عملیات در انتهای فهرست هیچ‌چیز را جابجا نمی‌کند و O(1) است.

© حق نشر 2001 Python Software Foundation.
این صفحه تحت مجوز بنیاد نرم‌افزار پایتون نسخه ۲ منتشر شده است.
مثال‌ها، دستورالعمل‌ها، و سایر کدهای موجود در مستندات همچنین تحت مجوز بدون بند BSD منتشر شده‌اند.
برای اطلاعات بیشتر به تاریخچه و مجوز مراجعه کنید.

بنیاد نرم‌افزار پایتون یک شرکت غیرانتفاعی است. لطفاً کمک مالی کنید.

آخرین به‌روزرسانی در نوامبر 12, 2026 (06:19 UTC). آیا اشکالی یافتید؟
ساخته شده با Sphinx 9.1.0.

You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.

GeezerVison

پیچیدگی زمانی عملیات‌ها روی انواع توکار¶

list¶

tuple¶

dict, frozendict¶

set, frozenset¶

str, bytes, bytearray¶

memoryview¶

range¶