در این ویدیو با استفاده از الگوریتم top one مقادیری که در یک آرایه بیشترین تکرار را داشته‌اند را پیدا میکنیم
در این ویدیو با استفاده از الگوریتم top one مقادیری که در یک آرایه بیشترین تکرار را داشته‌اند را پیدا میکنیم
سلام واسم سواله چرا الگوریتم اینجا میشه o(n)
مگه دوبار پیمایش نکردیم نباید میشد polynomial؟
ارسال نظر
سلام
توی این الگوریتم دوبار روی ورودی پیمایش کردیم؟
درود
با توجه به اینکه فرمودین بهتره که برای الگوریتم نویسی از امکانات یک زبان استفاده نکنیم و اینکه در حل این مساله از max استفاده شده بود بنده سعی کردم بدون استفاده ازش مساله را حل کنم که کدش به این صورت شد
def top(arr):
obj = {}
top_val = 0
result = []
for i in arr:
if i in obj:
obj[i] += 1
else:
obj[i] = 1
for k, v in obj.items():
flag = False
if v > top_val:
top_val = v
if result and flag:
result.clear()
elif result:
result.pop()
result.append(k)
else:
result.append(k)
elif v == top_val:
result.append(k)
flag = True
else:
continue
return result
ارسال نظر
سلام کامپلکسیتی این الگوریتم o(n^n) polynomialهست چون روبار مجبور شریم پیمایش کنید با حلقه؟
ارسال نظر
سلام
خیر، o(n) هست. توی ویدیو هم مشخصه
خسته نباشید. تو حلقه اول اومدیم شرط نوشتیم و گفتیم اگه داخل ولیوز بود ...
نکته ای که هست به نظرم اینه که خود in هم میاد یک بار دیکشنری رو پیمایش میکنه. در نتیجه ما الان به نوعی داریم داخل پیمایش اول که for هست یه پیمایش دیگه که in هست اینجام میدیم و به نظرم این داره کامپلکسیتی o(n^2) میده. در نتیجه کامپلیکسیتی الگوریتممون هم o(n^2) میشه.
ارسال نظر
سلام
خیر، تابع in داخل دیکشنری پیمایش نمیکنه. دیکشنری hash container هست و استفاده از in داخل دیکشنری معمولا o(1) هست
سلام . تعریف اولیه f_val چه سودی داره ؟ چون وقتیحذفش میکنی باز هم کار میکنه
منظورم اونجا که نوشتید f_val=0
ارسال نظر
آره دقیقا سودی نداشت
میشد تعریفش نکرد اون اول
سلام.اگر تو الگوریتمی که میشد به جای for زدن از map استفاده کرد-آیا تایم کامپلکستی بهتر میشه توی map به جای for?
ارسال نظر
سلام
بله. بهتره از map استفاده کنید
سلام.ممنون برای ویدیو ها -آیا از نظر تایم کامپلکتیسی و مصرف منابع استفاده از حلقه for روی خود لیست بهتره یا روی range(len(list)) لیست بهتره ؟ و آیا این دوتا از نظر آیا از نظر تایم کامپلکتیسی و مصرف منابع فرقی دارند؟
ارسال نظر
سلام
فرقی ندارن
ارسال نظر