۰
subtitle
ارسال: #۱
  
یافتن i عنصر بزرگ در آرایه.
سلام.
درست است یا نه؟ ی
۱- استفاده از مرتب سازی : nlogn
۲- استفاده از یک هیپ و i بار extract max : م n + i log i
۳- یافتن i امین عنصر (مرتبه n) و تقسیم بر اساس آن و مرتب سازی i عدد بزرگ : n + i log i
درست است یا نه؟ ی
۱- استفاده از مرتب سازی : nlogn
۲- استفاده از یک هیپ و i بار extract max : م n + i log i
۳- یافتن i امین عنصر (مرتبه n) و تقسیم بر اساس آن و مرتب سازی i عدد بزرگ : n + i log i
۲
ارسال: #۲
  
RE: یافتن i عنصر بزرگ در آرایه.
(۱۷ بهمن ۱۳۹۲ ۱۲:۰۵ ق.ظ)e.shrm نوشته شده توسط: سلام.اولی درست
درست است یا نه؟ ی
۱- استفاده از مرتب سازی : nlogn
۲- استفاده از یک هیپ و i بار extract max : م n + i log i
۳- یافتن i امین عنصر (مرتبه n) و تقسیم بر اساس آن و مرتب سازی i عدد بزرگ : n + i log i
دومی n+ilogn
سومی به نظرم درسته ولی یه کار بهتر اینکه فقط i امین عنصر را پیدا کنیم و بدیمش به پارتیشن و پاریتیشن هم عناصر بزرگتر از i را ببره طرف راستش. حالا ما طرف راست عناصر بزرگتر از i را داریم و دیگه نیازی به مرتب سازی هم نداریم و مرتبه میشه n برای پیدا کردن عنصر i و n هم برای پارتیشن و در کل ۲n
ارسال: #۳
  
RE: یافتن i عنصر بزرگ در آرایه.
(۱۷ بهمن ۱۳۹۲ ۱۲:۱۰ ق.ظ)masoud67 نوشته شده توسط:ممنون. برای دومی اینو ببینید :(17 بهمن ۱۳۹۲ ۱۲:۰۵ ق.ظ)e.shrm نوشته شده توسط: سلام.اولی درست
درست است یا نه؟ ی
۱- استفاده از مرتب سازی : nlogn
۲- استفاده از یک هیپ و i بار extract max : م n + i log i
۳- یافتن i امین عنصر (مرتبه n) و تقسیم بر اساس آن و مرتب سازی i عدد بزرگ : n + i log i
دومی n+ilogn
سومی به نظرم درسته ولی یه کار بهتر اینکه فقط i امین عنصر را پیدا کنیم و بدیمش به پارتیشن و پاریتیشن هم عناصر بزرگتر از i را ببره طرف راستش. حالا ما طرف راست عناصر بزرگتر از i را داریم و دیگه نیازی به مرتب سازی هم نداریم و مرتبه میشه n برای پیدا کردن عنصر i و n هم برای پارتیشن و در کل ۲n
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
ارسال: #۴
  
RE: یافتن i عنصر بزرگ در آرایه.
(۱۷ بهمن ۱۳۹۲ ۱۲:۱۰ ق.ظ)masoud67 نوشته شده توسط:(17 بهمن ۱۳۹۲ ۱۲:۰۵ ق.ظ)e.shrm نوشته شده توسط: سلام.اولی درست
درست است یا نه؟ ی
۱- استفاده از مرتب سازی : nlogn
۲- استفاده از یک هیپ و i بار extract max : م n + i log i
۳- یافتن i امین عنصر (مرتبه n) و تقسیم بر اساس آن و مرتب سازی i عدد بزرگ : n + i log i
دومی n+ilogn
سومی به نظرم درسته ولی یه کار بهتر اینکه فقط i امین عنصر را پیدا کنیم و بدیمش به پارتیشن و پاریتیشن هم عناصر بزرگتر از i را ببره طرف راستش. حالا ما طرف راست عناصر بزرگتر از i را داریم و دیگه نیازی به مرتب سازی هم نداریم و مرتبه میشه n برای پیدا کردن عنصر i و n هم برای پارتیشن و در کل ۲n
برای مورد سوم من میگم میشه i*n. وگرنه طبق گفته شما میشه n^2 نه ۲n.
ارسال: #۵
  
RE: یافتن i عنصر بزرگ در آرایه.
ارسال: #۶
  
RE: یافتن i عنصر بزرگ در آرایه.
(۱۷ بهمن ۱۳۹۲ ۰۸:۰۵ ق.ظ)e.shrm نوشته شده توسط:(17 بهمن ۱۳۹۲ ۰۷:۴۹ ق.ظ)fulgent نوشته شده توسط: برای مورد سوم من میگم میشه i*n. وگرنه طبق گفته شما میشه n^2 نه ۲n.
چرا؟! i امین رو که پیدا کنیم تو n ، کافیه حول اون پارتیشن کنیم ، اونوقت هرچی از i بیشتر میره بالا دیگه ؟
واسه دومی به نظر من میشه [tex]n (\lg n \lg (n-1) \dots \lg(n - i 1) )[/tex]
ولی نمیدونم اینو ساده کنیم به اون چیزی که شما میگی میرسیم یا نه!
ولی یه طوری میشه چک کنی که شما اگه n تا عدد اول رو بکشی بیرون بیاد یه چیزی حدود nlgn بشه که اونم میشه! و اون چیزی که من نوشتم هم فکر کنم بشه
[tex]n \lg(n!) = n n\lg n \in \Omega(n\lg n)[/tex]
ارسال: #۷
  
RE: یافتن i عنصر بزرگ در آرایه.
(۱۷ بهمن ۱۳۹۲ ۱۲:۳۰ ق.ظ)e.shrm نوشته شده توسط: ممنون. برای دومی اینو ببینید :برای دومی من پیش فرض i را کوچک و ثابت فرض کردم. تو این سوال i را وابسته به n گرفته و خودش گفته i بیشتر از n/2 . پس به جای n میشه i هم گذاشت. عبارت دقیقشو باید حساب کرد که بازم بعید میدونم ilogi بشه .
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
ارسال: #۸
  
RE: یافتن i عنصر بزرگ در آرایه.
(۱۷ بهمن ۱۳۹۲ ۱۲:۱۰ ق.ظ)masoud67 نوشته شده توسط:اینکه میگین i عنصر درآخر نیاز به مرتب سازی نداره، بخاطر اینه که سوال نمیخواد دقیقا بدونه مثلا دومین بزرگترین عنصر دقیقا چه عنصری هست؟(17 بهمن ۱۳۹۲ ۱۲:۰۵ ق.ظ)e.shrm نوشته شده توسط: سلام.اولی درست
درست است یا نه؟ ی
۱- استفاده از مرتب سازی : nlogn
۲- استفاده از یک هیپ و i بار extract max : م n + i log i
۳- یافتن i امین عنصر (مرتبه n) و تقسیم بر اساس آن و مرتب سازی i عدد بزرگ : n + i log i
دومی n+ilogn
سومی به نظرم درسته ولی یه کار بهتر اینکه فقط i امین عنصر را پیدا کنیم و بدیمش به پارتیشن و پاریتیشن هم عناصر بزرگتر از i را ببره طرف راستش. حالا ما طرف راست عناصر بزرگتر از i را داریم و دیگه نیازی به مرتب سازی هم نداریم و مرتبه میشه n برای پیدا کردن عنصر i و n هم برای پارتیشن و در کل ۲n
۰
۰
ارسال: #۱۰
  
RE: یافتن i عنصر بزرگ در آرایه.
به نظر منم n+ilogi درسته وهمیشه جواب می ده!
این سوال مثل سوال ۱۱۲ هست من امروز صبح در این قسمت آخر page نوشتمش و توضیحم بر اساس توضیحاتیه که دکتر یوسفی گفتن:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
فقط تو اونجا k تا کوچکه رو می خواسته اینجا i تا بزرگتر رو!
این سوال مثل سوال ۱۱۲ هست من امروز صبح در این قسمت آخر page نوشتمش و توضیحم بر اساس توضیحاتیه که دکتر یوسفی گفتن:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
فقط تو اونجا k تا کوچکه رو می خواسته اینجا i تا بزرگتر رو!
ارسال: #۱۱
  
RE: یافتن i عنصر بزرگ در آرایه.
(۱۷ بهمن ۱۳۹۲ ۱۰:۱۳ ب.ظ)mahsalove نوشته شده توسط: به نظر منم n+ilogi درسته وهمیشه جواب می ده!
این سوال مثل سوال ۱۱۲ هست من امروز صبح در این قسمت آخر page نوشتمش و توضیحم بر اساس توضیحاتیه که دکتر یوسفی گفتن:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
فقط تو اونجا k تا کوچکه رو می خواسته اینجا i تا بزرگتر رو!
یکی لطف میکنه به من توضیح بده چطوری هیپ رو تو تتای n میسازن؟؟
ارسال: #۱۲
  
RE: یافتن i عنصر بزرگ در آرایه.
(۱۹ بهمن ۱۳۹۲ ۱۱:۳۳ ب.ظ)Good! نوشته شده توسط: یکی لطف میکنه به من توضیح بده چطوری هیپ رو تو تتای n میسازن؟؟اگر از روش درج متوالی استفاده بشه از مرتبه nlgn میشه اما روش دیگهای وجود داره که از آخرین گرهی پدر (یعنی پایینترین و سمت راستترین پدر) شروه به هیپ کردن درخت میکنه که این روش از مرتبه n هستش. تو CLRS فصل heapsort کاملا توضیح داده
ارسال: #۱۳
  
RE: یافتن i عنصر بزرگ در آرایه.
(۱۹ بهمن ۱۳۹۲ ۱۱:۳۸ ب.ظ)mfXpert نوشته شده توسط:(19 بهمن ۱۳۹۲ ۱۱:۳۳ ب.ظ)Good! نوشته شده توسط: یکی لطف میکنه به من توضیح بده چطوری هیپ رو تو تتای n میسازن؟؟اگر از روش درج متوالی استفاده بشه از مرتبه nlgn میشه اما روش دیگهای وجود داره که از آخرین گرهی پدر (یعنی پایینترین و سمت راستترین پدر) شروه به هیپ کردن درخت میکنه که این روش از مرتبه n هستش. تو CLRS فصل heapsort کاملا توضیح داده
این مشابه همون روش جوانترین پدر هست؟البته روش جوانترین پدر n log n هست.
ممنون ولی کامل متوجه نشدم.مثلا اینکه آخرین گره پدر رو چطور پیدا میکنه؟و اینکه بعدا بخواد پدر همین آخرین پدر رو با بچه هاش مقایسه کنه اگه اون آخرین پدر با پدرش جاش عوض بشه و اونوقت باعث بشه که همینطوری تا پایین جاشون عوض شه میشه همونn log n که
when all elements are distinct, the best-case running time of heapsort
is (n lg n).
این جمله از CLRS هست.میشه شما بگید کدوم صفحه اون روش رو نوشته؟
ارسال: #۱۴
  
RE: یافتن i عنصر بزرگ در آرایه.
(۲۰ بهمن ۱۳۹۲ ۱۲:۱۷ ق.ظ)Good! نوشته شده توسط: این مشابه همون روش جوانترین پدر هست؟البته روش جوانترین پدر n log n هست.این دقیقا همونه که در ظاهر n/2 بار تابع maxheap را که مرتبه logn داره را فراخوانی میکنه. و به ظاهر میشه nlogn
ممنون ولی کامل متوجه نشدم.مثلا اینکه آخرین گره پدر رو چطور پیدا میکنه؟و اینکه بعدا بخواد پدر همین آخرین پدر رو با بچه هاش مقایسه کنه اگه اون آخرین پدر با پدرش جاش عوض بشه و اونوقت باعث بشه که همینطوری تا پایین جاشون عوض شه میشه همونn log n که
when all elements are distinct, the best-case running time of heapsort
is (n lg n).
این جمله از CLRS هست.میشه شما بگید کدوم صفحه اون روش رو نوشته؟
اما اگه دقیقتر حساب بشه میشه مرتبه n چون در هر ارتفاعی maxheap یه مرتبه به خصوصی داره و همیشه logn نیست
من فایل اثباتشو ضمیمه کردم و اینجا هم هست
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
و برای سوال دوم موضوع اصلی تاپیک هم ، این سوال و جواب را از تمرینات CLRS پیدا کردم
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
ارسال: #۱۵
  
RE: یافتن i عنصر بزرگ در آرایه.
(۲۰ بهمن ۱۳۹۲ ۱۲:۴۸ ق.ظ)masoud67 نوشته شده توسط:(20 بهمن ۱۳۹۲ ۱۲:۱۷ ق.ظ)Good! نوشته شده توسط: این مشابه همون روش جوانترین پدر هست؟البته روش جوانترین پدر n log n هست.این دقیقا همونه که در ظاهر n/2 بار تابع maxheap را که مرتبه logn داره را فراخوانی میکنه. و به ظاهر میشه nlogn
ممنون ولی کامل متوجه نشدم.مثلا اینکه آخرین گره پدر رو چطور پیدا میکنه؟و اینکه بعدا بخواد پدر همین آخرین پدر رو با بچه هاش مقایسه کنه اگه اون آخرین پدر با پدرش جاش عوض بشه و اونوقت باعث بشه که همینطوری تا پایین جاشون عوض شه میشه همونn log n که
when all elements are distinct, the best-case running time of heapsort
is (n lg n).
این جمله از CLRS هست.میشه شما بگید کدوم صفحه اون روش رو نوشته؟
اما اگه دقیقتر حساب بشه میشه مرتبه n چون در هر ارتفاعی maxheap یه مرتبه به خصوصی داره و همیشه logn نیست
من فایل اثباتشو ضمیمه کردم و اینجا هم هست
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
و برای سوال دوم موضوع اصلی تاپیک هم ، این سوال و جواب را از تمرینات CLRS پیدا کردم
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
واقعا لطف کردید.ممنون.گرچه اون اولی دو خط آخر اثباتشو متوجه نشدم
ارسال: #۱۶
  
RE: یافتن i عنصر بزرگ در آرایه.
ارسال: #۱۷
  
RE: یافتن i عنصر بزرگ در آرایه.
(۲۰ بهمن ۱۳۹۲ ۰۹:۰۴ ق.ظ)masoud67 نوشته شده توسط:(20 بهمن ۱۳۹۲ ۰۱:۱۱ ق.ظ)Good! نوشته شده توسط: واقعا لطف کردید.ممنون.گرچه اون اولی دو خط آخر اثباتشو متوجه نشدمچون h مقدار خطی و [tex]2^{h}[/tex] مقدار نمایی هست و مقدار h خیلی از کمتر مقدار نمایی میشه ، h را یک در نظر گرفته و بقیه اش دیگه واضحه
تشکر گرچه بازم متوجه نشدم.طریقه به دست آوردن یک دوم به توان h رو متوجه میشم اما اون خط آخر که تو مخرج ۱ منهای ۱/۲ به توان ۲ هست رو متوجه نمیشم
در ضمن جوابی که شما از clrs پیدا کردید نوشته n+ilogn در صورتیکه یکی دیگه از دوستان یه جواب از کتاب دیگه ای گذاشتن که n+ilogi بود.حالا کدوم درسته؟؟:؟
ارسال: #۱۸
  
RE: یافتن i عنصر بزرگ در آرایه.
(۲۱ بهمن ۱۳۹۲ ۱۲:۵۸ ق.ظ)Good! نوشته شده توسط: تشکر گرچه بازم متوجه نشدم.طریقه به دست آوردن یک دوم به توان h رو متوجه میشم اما اون خط آخر که تو مخرج ۱ منهای ۱/۲ به توان ۲ هست رو متوجه نمیشمخودتو درگیرش نکن. بدیهی بگیر برو
در ضمن جوابی که شما از clrs پیدا کردید نوشته n+ilogn در صورتیکه یکی دیگه از دوستان یه جواب از کتاب دیگه ای گذاشتن که n+ilogi بود.حالا کدوم درسته؟؟:؟
سوالی که من گذاشتم (که نباید میذاشتم) واسه زمانی بود که i عدد ثابت هست ولی صورت سوالی که دوستمون گذاشته بودند (نه در پست اول ، بلکه چند تا پست پایین تر) i وابسته n بوده به همین خاطر به جای n میتونیم i بذاریم که دقیقتر میشه
ارسال: #۱۹
  
RE: یافتن i عنصر بزرگ در آرایه.
(۲۱ بهمن ۱۳۹۲ ۰۸:۰۶ ق.ظ)masoud67 نوشته شده توسط:اوکی پس ینی جواب سوال اولین پست میشه n+ilogn ولی اونی که i رو وابسته به n گرفته میشه n+ilogi?(21 بهمن ۱۳۹۲ ۱۲:۵۸ ق.ظ)Good! نوشته شده توسط: تشکر گرچه بازم متوجه نشدم.طریقه به دست آوردن یک دوم به توان h رو متوجه میشم اما اون خط آخر که تو مخرج ۱ منهای ۱/۲ به توان ۲ هست رو متوجه نمیشمخودتو درگیرش نکن. بدیهی بگیر برو
در ضمن جوابی که شما از clrs پیدا کردید نوشته n+ilogn در صورتیکه یکی دیگه از دوستان یه جواب از کتاب دیگه ای گذاشتن که n+ilogi بود.حالا کدوم درسته؟؟:؟
سوالی که من گذاشتم (که نباید میذاشتم) واسه زمانی بود که i عدد ثابت هست ولی صورت سوالی که دوستمون گذاشته بودند (نه در پست اول ، بلکه چند تا پست پایین تر) i وابسته n بوده به همین خاطر به جای n میتونیم i بذاریم که دقیقتر میشه
اوکی ممنون
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
تکمیل قطعه کد مجموع آرایه | Xzrix | ۰ | ۱,۵۰۱ |
۰۲ دى ۱۳۹۹ ۰۷:۱۹ ب.ظ آخرین ارسال: Xzrix |
|
یادگیری برنامه نویسی تا اجرای پروژه های بزرگ | The BesT | ۳ | ۳,۶۷۵ |
۱۲ آذر ۱۳۹۸ ۰۳:۵۸ ب.ظ آخرین ارسال: marvelous |
|
مرتبه زمانی یافتن قطر | Sepideh96 | ۲ | ۳,۸۲۷ |
۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ آخرین ارسال: erfan30 |
|
کتابهای بزرگ جهان را بخوانید! | marvelous | ۷ | ۵,۳۴۴ |
۰۵ مرداد ۱۳۹۸ ۰۳:۵۸ ب.ظ آخرین ارسال: marvelous |
|
کتابهای بزرگ جهان را بخوانید! | marvelous | ۰ | ۱,۹۰۳ |
۰۲ مرداد ۱۳۹۸ ۰۲:۵۷ ب.ظ آخرین ارسال: marvelous |
|
Pointer C++ آرایه کمک فوری ... | porseshgar | ۰ | ۱,۶۸۵ |
۰۳ اسفند ۱۳۹۷ ۰۲:۵۹ ب.ظ آخرین ارسال: porseshgar |
|
یافتن دو عدد پیچیدگی زمانی O(n) | porseshgar | ۲ | ۳,۹۶۱ |
۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ آخرین ارسال: porseshgar |
|
آرایه نامرتب | Sanazzz | ۴ | ۴,۴۳۶ |
۰۴ بهمن ۱۳۹۷ ۱۱:۴۹ ب.ظ آخرین ارسال: Sanazzz |
|
محاسبه چندمین عنصر آرایه | Mr.R3ZA | ۶ | ۶,۷۵۲ |
۱۹ شهریور ۱۳۹۷ ۰۸:۱۲ ب.ظ آخرین ارسال: Saman |
|
تولید آرایه تصادفی | αɾια | ۴ | ۴,۶۹۴ |
۰۴ تیر ۱۳۹۷ ۰۵:۳۹ ق.ظ آخرین ارسال: Behnam |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close