۰
subtitle
ارسال: #۱
  
پیچیدگی زمانی علوم کامپیوتر ۸۸
اگر n عدد صحیح داشته باشیم , که یکی از آنها x باشد,الگوریتمی که تشخیص دهددو عدد در این اعداد وجود دارد که مجموع این دو عدد دقیقا" x می باشد,دارای کدام پیچیدگی زمانی است ؟؟
۱-[tex]O(log n)[/tex]
۲-[tex]O(n log n)[/tex]
۳-[tex]O(n^{2})[/tex]
۴-[tex]O(n)[/tex]
۱-[tex]O(log n)[/tex]
۲-[tex]O(n log n)[/tex]
۳-[tex]O(n^{2})[/tex]
۴-[tex]O(n)[/tex]
۲
ارسال: #۲
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
اول آرایه رو مرتب می کنیم در زمان [tex]O(nlogn)[/tex]
بعد با جستجوی دودویی X رو پیدا می کنیم در [tex]O(logn)[/tex]
اعداد بزرگتر از x که هیچ، برای کوچکترها دو تا شمارنده i و j می گیریم که یکی(i) از عنصر اول شروع می کنه و جلو میره، یکی دیگه(j) از عنصر ماقبل x شروع می کنه و به سمت عقب میره
هر بار [tex]A[i] A[j][/tex] رو محاسبه می کنیم؛ اگر کمتر از x بود به i یک واحد اضافه می کنیم؛ اگر بیشتر از x بود از j یک واحد کم می کنیم و این بررسی رو اونقدر ادامه می دیم تا یا جواب رو بدست بیاریم ؛ یا [tex]i>j[/tex] که در این صورت fail رو بر می گردونه
این کارهای جستجو هم زمان [tex]O(n)[/tex] صرف می کنن حداکثر
جواب کل میشه [tex]O(nlogn)[/tex]
بعد با جستجوی دودویی X رو پیدا می کنیم در [tex]O(logn)[/tex]
اعداد بزرگتر از x که هیچ، برای کوچکترها دو تا شمارنده i و j می گیریم که یکی(i) از عنصر اول شروع می کنه و جلو میره، یکی دیگه(j) از عنصر ماقبل x شروع می کنه و به سمت عقب میره
هر بار [tex]A[i] A[j][/tex] رو محاسبه می کنیم؛ اگر کمتر از x بود به i یک واحد اضافه می کنیم؛ اگر بیشتر از x بود از j یک واحد کم می کنیم و این بررسی رو اونقدر ادامه می دیم تا یا جواب رو بدست بیاریم ؛ یا [tex]i>j[/tex] که در این صورت fail رو بر می گردونه
این کارهای جستجو هم زمان [tex]O(n)[/tex] صرف می کنن حداکثر
جواب کل میشه [tex]O(nlogn)[/tex]
ارسال: #۳
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
(۱۸ بهمن ۱۳۹۲ ۰۸:۴۶ ب.ظ)tayebe68 نوشته شده توسط: اول آرایه رو مرتب می کنیم در زمان [tex]O(nlogn)[/tex]
بعد با جستجوی دودویی X رو پیدا می کنیم در [tex]O(n)[/tex]
اعداد بزرگتر از x که هیچ، برای کوچکترها دو تا شمارنده i و j می گیریم که یکی(i) از عنصر اول شروع می کنه و جلو میره، یکی دیگه(j) از عنصر ماقبل x شروع می کنه و به سمت عقب میره
هر بار [tex]A[i] A[j][/tex] رو محاسبه می کنیم؛ اگر کمتر از x بود به i یک واحد اضافه می کنیم؛ اگر بیشتر از x بود از j یک واحد کم می کنیم و این بررسی رو اونقدر ادامه می دیم تا یا جواب رو بدست بیاریم ؛ یا [tex]i>j[/tex] که در این صورت fail رو بر می گردونه
این کارهای جستجو هم زمان [tex]O(n)[/tex] صرف می کنن حداکثر
جواب کل میشه [tex]O(nlogn)[/tex]
زمان جستجوی دودویی میشه از مرتبه log n. مگه نه؟
(۱۸ بهمن ۱۳۹۲ ۰۸:۴۸ ب.ظ)explorer نوشته شده توسط:(05 بهمن ۱۳۹۲ ۰۶:۱۹ ب.ظ)tabassomesayna نوشته شده توسط: اگر n عدد صحیح داشته باشیم , که یکی از آنها x باشد,الگوریتمی که تشخیص دهددو عدد در این اعداد وجود دارد که مجموع این دو عدد دقیقا" x می باشد,دارای کدام پیچیدگی زمانی است ؟؟
۱-[tex]O(log n)[/tex]
۲-[tex]O(n log n)[/tex]
۳-[tex]O(n^{2})[/tex]
۴-[tex]O(n)[/tex]
شما عمل پارتیشن رو حول x انجام بده O (n)
حالا سمت چپ x اعداد کوچکتر از x هستند
با nlogn مرتب میشن
حالا به ازای هر عنصر مثه y ، عنصر x-y رو توی قسمت چپ x سرچ میکنیم
کلا nlogn میشه
اعداد کوچکتر از x رو در زمان nlogn مرتب نمی کنند زمانش کمتر میشه...
ارسال: #۴
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
ارسال: #۵
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
(۱۸ بهمن ۱۳۹۲ ۰۸:۴۶ ب.ظ)tayebe68 نوشته شده توسط: اول آرایه رو مرتب می کنیم در زمان [tex]O(nlogn)[/tex]جوابتون دقیقا درسته ولی یه اشتباه کوچیک داره گفتم شما توجه نکردین بد نیست بگم که تو جلسه اشتباه نکنین
بعد با جستجوی دودویی X رو پیدا می کنیم در [tex]O(logn)[/tex]
اعداد بزرگتر از x که هیچ، برای کوچکترها دو تا شمارنده i و j می گیریم که یکی(i) از عنصر اول شروع می کنه و جلو میره، یکی دیگه(j) از عنصر ماقبل x شروع می کنه و به سمت عقب میره
هر بار [tex]A[i] A[j][/tex] رو محاسبه می کنیم؛ اگر کمتر از x بود به i یک واحد اضافه می کنیم؛ اگر بیشتر از x بود از j یک واحد کم می کنیم و این بررسی رو اونقدر ادامه می دیم تا یا جواب رو بدست بیاریم ؛ یا [tex]i>j[/tex] که در این صورت fail رو بر می گردونه
این کارهای جستجو هم زمان [tex]O(n)[/tex] صرف می کنن حداکثر
جواب کل میشه [tex]O(nlogn)[/tex]
عداد آرایه صیح هست با O(m+n)l آرایه مرتب میشه بعد مراحلی که tayebe68 گفتند
بعد با جستجوی دودویی X رو پیدا می کنیم در [tex]O(logn)[/tex]
اعداد بزرگتر از x که هیچ، برای کوچکترها دو تا شمارنده i و j می گیریم که یکی(i) از عنصر اول شروع می کنه و جلو میره، یکی دیگه(j) از عنصر ماقبل x شروع می کنه و به سمت عقب میره
هر بار [tex]A[i] A[j][/tex] رو محاسبه می کنیم؛ اگر کمتر از x بود به i یک واحد اضافه می کنیم؛ اگر بیشتر از x بود از j یک واحد کم می کنیم و این بررسی رو اونقدر ادامه می دیم تا یا جواب رو بدست بیاریم ؛ یا [tex]i>j[/tex] که در این صورت fail رو بر می گردونه
اجرا میشه و بعد از مرتبه o(n)l میشه
ارسال: #۶
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
(۱۹ بهمن ۱۳۹۲ ۰۲:۲۳ ب.ظ)mohammad.ardeshiri نوشته شده توسط:(18 بهمن ۱۳۹۲ ۰۸:۴۶ ب.ظ)tayebe68 نوشته شده توسط: اول آرایه رو مرتب می کنیم در زمان [tex]O(nlogn)[/tex]جوابتون دقیقا درسته ولی یه اشتباه کوچیک داره گفتم شما توجه نکردین بد نیست بگم که تو جلسه اشتباه نکنین
بعد با جستجوی دودویی X رو پیدا می کنیم در [tex]O(logn)[/tex]
اعداد بزرگتر از x که هیچ، برای کوچکترها دو تا شمارنده i و j می گیریم که یکی(i) از عنصر اول شروع می کنه و جلو میره، یکی دیگه(j) از عنصر ماقبل x شروع می کنه و به سمت عقب میره
هر بار [tex]A[i] A[j][/tex] رو محاسبه می کنیم؛ اگر کمتر از x بود به i یک واحد اضافه می کنیم؛ اگر بیشتر از x بود از j یک واحد کم می کنیم و این بررسی رو اونقدر ادامه می دیم تا یا جواب رو بدست بیاریم ؛ یا [tex]i>j[/tex] که در این صورت fail رو بر می گردونه
این کارهای جستجو هم زمان [tex]O(n)[/tex] صرف می کنن حداکثر
جواب کل میشه [tex]O(nlogn)[/tex]
عداد آرایه صیح هست با O(m+n)l آرایه مرتب میشه بعد مراحلی که tayebe68 گفتند
بعد با جستجوی دودویی X رو پیدا می کنیم در [tex]O(logn)[/tex]
اعداد بزرگتر از x که هیچ، برای کوچکترها دو تا شمارنده i و j می گیریم که یکی(i) از عنصر اول شروع می کنه و جلو میره، یکی دیگه(j) از عنصر ماقبل x شروع می کنه و به سمت عقب میره
هر بار [tex]A[i] A[j][/tex] رو محاسبه می کنیم؛ اگر کمتر از x بود به i یک واحد اضافه می کنیم؛ اگر بیشتر از x بود از j یک واحد کم می کنیم و این بررسی رو اونقدر ادامه می دیم تا یا جواب رو بدست بیاریم ؛ یا [tex]i>j[/tex] که در این صورت fail رو بر می گردونه
اجرا میشه و بعد از مرتبه o(n)l میشه
با استفاده از مرتب سازی شمارشی به o(m+n) l رسیدین پس جواب کلی o(n)l هست؟
ارسال: #۷
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
ما اینجا نمیتونیم از Count Sort استفاده کنیم
یعنی نه اینکه نتونیما میتونیم ولی فایده نداره چون فقط اعداد صحیحن و معلوم نیس در چه بازه ای هستن مثلا ممکنه یه عدد n رقمی باشه و این الگوریتم میشه n^2
پس همون مرتب سازی مبتنی بر مقایسه بهتره
یعنی نه اینکه نتونیما میتونیم ولی فایده نداره چون فقط اعداد صحیحن و معلوم نیس در چه بازه ای هستن مثلا ممکنه یه عدد n رقمی باشه و این الگوریتم میشه n^2
پس همون مرتب سازی مبتنی بر مقایسه بهتره
ارسال: #۸
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
(۱۹ بهمن ۱۳۹۲ ۰۳:۴۶ ب.ظ)hosshah نوشته شده توسط: ما اینجا نمیتونیم از Count Sort استفاده کنیم
یعنی نه اینکه نتونیما میتونیم ولی فایده نداره چون فقط اعداد صحیحن و معلوم نیس در چه بازه ای هستن مثلا ممکنه یه عدد n رقمی باشه و این الگوریتم میشه n^2
پس همون مرتب سازی مبتنی بر مقایسه بهتره
خب پس زمان مرتب سازی رو چه جوری حساب کردین
ارسال: #۹
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
ارسال: #۱۰
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
ارسال: #۱۱
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
(۱۹ بهمن ۱۳۹۲ ۰۳:۴۶ ب.ظ)hosshah نوشته شده توسط: ما اینجا نمیتونیم از Count Sort استفاده کنیممگه radix هست که با اعداد n رقمی بشه n^2 ? اون radix هست که با عدد n رقمی میشه n^2
یعنی نه اینکه نتونیما میتونیم ولی فایده نداره چون فقط اعداد صحیحن و معلوم نیس در چه بازه ای هستن مثلا ممکنه یه عدد n رقمی باشه و این الگوریتم میشه n^2
پس همون مرتب سازی مبتنی بر مقایسه بهتره
ولی حرفت در کل درسته ولی من الان بیشتر فکر کردم یعنی یه نیم ساعتی فکر کردم دیدم اصن جوال
(n/2)^ دو
میشه
شما حتی اگه با n هم مرتب کنی ونصفشو تو حالت متوسط بندازی بیرون
بازم n/2 میمونه که باید دو تا حلقه for بزاری به ازای هر i تمام j هارو برسی کنی که میشه n^2
ارسال: #۱۲
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
(۲۱ بهمن ۱۳۹۲ ۰۲:۴۰ ب.ظ)mohammad.ardeshiri نوشته شده توسط: مگه radix هست که با اعداد n رقمی بشه n^2 ? اون radix هست که با عدد n رقمی میشه n^2
ولی حرفت در کل درسته ولی من الان بیشتر فکر کردم یعنی یه نیم ساعتی فکر کردم دیدم اصن جوال
(n/2)^ دو
میشه
شما حتی اگه با n هم مرتب کنی ونصفشو تو حالت متوسط بندازی بیرون
بازم n/2 میمونه که باید دو تا حلقه for بزاری به ازای هر i تمام j هارو برسی کنی که میشه n^2
خب نه من منظورم از Count به تعداد n رقم تا بود دیگه که میشه همون radix میشه از مرتبه n^2
ولی کل الگوریتم از مرتبه همون nlogn ها!!!
اون حلقه ای که میخواد عددا رو پیدا کنه یه حلقه ست نه دو حلقه
ارسال: #۱۳
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
(۲۱ بهمن ۱۳۹۲ ۰۲:۴۰ ب.ظ)mohammad.ardeshiri نوشته شده توسط: شما حتی اگه با n هم مرتب کنی ونصفشو تو حالت متوسط بندازی بیرون
بازم n/2 میمونه که باید دو تا حلقه for بزاری به ازای هر i تمام j هارو برسی کنی که میشه n^2
چون برای اعداد بازه یا شرط خاصی معین نشده ، باید مرتب سازی مبتنی بر مقایسه داشته باشیم که بهترین زمانش میشه [tex]O(nlogn)[/tex]
اینجا چون که آرایه مرتبه نیازی نیست دو تا حلقه for بگیریم
این آرایه مرتب رو در نظر بگیرید [tex]\[2,4,5,7,9,11,13,15\][/tex] می خوایم دو عدد پیدا کنیم که مجموعشون بشه ۱۶: (فرض که j به ۱۵ اشاره می کنه، i به ۲):
اول ۲ و ۱۵ رو مقایسه می کنیم میشه ۱۷ که از ۱۶ بیشتره پس --j
حالا ۱۵=۲+۱۳ <16 پس ++i
بعدی ۱۷=۱۳+۴ >16 پس --j
بعدی ۱۵=۱۱+۴ <16 پس ++i
و در آخر ۱۶=۱۱+۵ که اینجا جواب رو پیدا کردیم، و زمان این جستجو [tex]O(n)[/tex] میشه حتی در بدترین حالت که x بزرگترین عنصر باشه
۰
ارسال: #۱۵
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
۰
ارسال: #۱۶
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
سلام اگه جواب میشه [tex]O(nlogn)[/tex] بگین من توضیحمو بدم (البته اگه این n عدد صخیخ در بازه ۰ تا n-1 باشن از مرتبه n میشه ولی چون چیزی تو صورت سوال نگفته همون nlogn میشه به نظرم)
۰
ارسال: #۱۷
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
(۰۵ بهمن ۱۳۹۲ ۰۶:۱۹ ب.ظ)tabassomesayna نوشته شده توسط: اگر n عدد صحیح داشته باشیم , که یکی از آنها x باشد,الگوریتمی که تشخیص دهددو عدد در این اعداد وجود دارد که مجموع این دو عدد دقیقا" x می باشد,دارای کدام پیچیدگی زمانی است ؟؟
۱-[tex]O(log n)[/tex]
۲-[tex]O(n log n)[/tex]
۳-[tex]O(n^{2})[/tex]
۴-[tex]O(n)[/tex]
شما عمل پارتیشن رو حول x انجام بده O (n)
حالا سمت چپ x اعداد کوچکتر از x هستند
با nlogn مرتب میشن
حالا به ازای هر عنصر مثه y ، عنصر x-y رو توی قسمت چپ x سرچ میکنیم
کلا nlogn میشه
ارسال: #۱۸
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
(۱۸ بهمن ۱۳۹۲ ۰۸:۴۸ ب.ظ)explorer نوشته شده توسط:(05 بهمن ۱۳۹۲ ۰۶:۱۹ ب.ظ)tabassomesayna نوشته شده توسط: اگر n عدد صحیح داشته باشیم , که یکی از آنها x باشد,الگوریتمی که تشخیص دهددو عدد در این اعداد وجود دارد که مجموع این دو عدد دقیقا" x می باشد,دارای کدام پیچیدگی زمانی است ؟؟
۱-[tex]O(log n)[/tex]
۲-[tex]O(n log n)[/tex]
۳-[tex]O(n^{2})[/tex]
۴-[tex]O(n)[/tex]
شما عمل پارتیشن رو حول x انجام بده O (n)
حالا سمت چپ x اعداد کوچکتر از x هستند
با nlogn مرتب میشن
حالا به ازای هر عنصر مثه y ، عنصر x-y رو توی قسمت چپ x سرچ میکنیم
کلا nlogn میشه
به نظرت نمیشه عملیات پارتیشن رو روی سمت چپ x ادامه بدیم؟به این صورت که دوباره پارتیشن بزنی و با میانه مقایشه کنیم اگر بازم میانه کوچکتر از x-y بود ادامه میدیم تا به عدد x-y برسیم اینطوری زمانش میشه o(n)....
نظرتونو بگید مرسی....
۰
ارسال: #۱۹
  
RE: پیچیدگی زمانی علوم کامپیوتر ۸۸
به دلیل ابهامی که تو سؤال پیش اومده بود، من این عکس رو میزارم، راه حل هم که دوستان خوب توضیح دادن
شماره تمرین رو یکی از دوستان زحمت کشیده بود گذاشته بود، من فقط پیداش کردم
شماره تمرین رو یکی از دوستان زحمت کشیده بود گذاشته بود، من فقط پیداش کردم
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close