Question [بایگانی] - برنامه نویس

yas1213

شنبه 10 اسفند 1387, 00:51 صبح

توضیح دهید چه توابعی در مجموعه های زیر وجود دارد؟

O(o(no(1)))
no(1)
o(no(1))

Developer Programmer

شنبه 10 اسفند 1387, 09:12 صبح

1) عنوان تاپیکتون رو مناسب با سئوال انتخاب کنید
2) منظور از no چیه ؟

shokoofeh68

پنج شنبه 15 اسفند 1387, 00:15 صبح

همان اوي كوچيكه ديگه
از سوالات فصل اول نيپوليتانه

manager

پنج شنبه 15 اسفند 1387, 11:46 صبح

سوال 29 فصل اول کتاب نیپولیتان.
البته ایشون حال درست تایپ کردن سوال رو نداشتند.
الف) (n^o(1
ب) ((O(n^o(1
ج) (((O(O(n^o(1

بهتره اول تکلیف (o(1 رو روشن کنیم. چه توابعی عضو این پیچیدگی زمانی هستند ؟
به نظرم به صورت زیر می شه ثابت کرد که فقط توابعی با زمان مصرفی صفر عضو این گروه هستند :

اگر f(n) ϵ o(1) می تونیم چنین نتیجه گیری کنیم که f(n) ≤ c و این بدین معنی است که تابع f یک تابع با پیچیدگی زمانی ثابت کوچکتر از c است. از آنجا که c هر عددی می تواند باشد و مطابق با تعریف o (اُی کوچک) به ازای هر n≥N رابطه فوق برای هر c بر قرار است. لذا نتیجه می گیریم که فقط توابعی با پیچیدگی زمانی صفر می توانند عضو o(1) باشند. این مطلب را می توان با استفاده از برهان خلف اثبات کرد.
من به درست بودن این اثبات شک دارم، در ضمن نمی دونم منظور از ((O(O(f چیه ! همینطور گزینه الف رو هم نمی فهمم یعنی چی ... !!

>> در ضمن بهتره شروع کننده تاپیک لطف کنه عنوان تاپیک رو تصحیح کنه ...

yas1213

شنبه 17 اسفند 1387, 01:44 صبح

نتیجتون درسته! ولی این که چه توابعی در اینا قرار دارن چی؟؟؟