19 دى 1390, 09:59 ب.ظ
19 دى 1390, 10:32 ب.ظ
(19 دى 1390 09:59 ب.ظ)vijay نوشته شده توسط: [ -> ]چون ارتفاع logn است پس مسیر بین u,vباید lognباشد یعنی به ارتفاع بستگی داشته باشد.
(استدلال من)
ولی جواب گزینه ۱می باشد.
ممنون میشم اگه کسی کمک کنه.
فرض کن u گره ای در آخرین سطح سمت چپ ریشه و v گره ای در آخرین سطح سمت راست ریشه یک درخت کامل باشه.
حالا باید در زمان logn پدر u رو پیدا کنیم که همون ریشه هست و در زمان logn فرزند ریشه رو که همون v هستش رو پیدا کنیم.
پس کلا در زمان (O(logn*logn میتونیم مسیر بین u و v رو پیدا کنیم.
البته در بدترین حالت مرتبش اینه. واسه همین از O استفاده کرده.
19 دى 1390, 10:38 ب.ظ
(19 دى 1390 10:32 ب.ظ)sasanlive نوشته شده توسط: [ -> ]فرض کن u گره ای در آخرین سطح سمت چپ ریشه و v گره ای در آخرین سطح سمت راست ریشه یک درخت کامل باشه.
حالا باید در زمان logn پدر u رو پیدا کنیم که همون ریشه هست و در زمان logn فرزند ریشه رو که همون v هستش رو پیدا کنیم.
پس کلا در زمان (O(logn*logn میتونیم مسیر بین u و v رو پیدا کنیم.
البته در بدترین حالت مرتبش اینه. واسه همین از O استفاده کرده.
خوب این چیزی که شما میگی میشه O(2Logn) و با گزینه دو جور در میاد.
19 دى 1390, 10:52 ب.ظ
(19 دى 1390 10:38 ب.ظ)pos نوشته شده توسط: [ -> ]خوب این چیزی که شما میگی میشه O(2Logn) و با گزینه دو جور در میاد.
در صورتی حرف شما درسته که بشه همزمان هر دو کارو طی زمانه logn حساب کرد.
ولی اینجا اول باید گره پدر رو پیدا کنیم با زمان logn و دوباره با زمان logn گره فرزند رو پیدا کنبم.نمیشه همزمان این دو کارو انجام داد. اول باید گره پدر رو مشخص کنیم.
پس باید مرتبهها رو ضرب کنیم نه جمع.
19 دى 1390, 11:08 ب.ظ
قانع نشدم اخوی. دو تا مشکل دارم:
1- درخت دودویی کامل هست نه درخت جستجوی دودویی پس نمیشه در logn مبدا و یا مقصد را پیدا کرد.
2- اگر هم بشه شما میگی یکبار مبدا را پیدا کنیم در زمان logn و بار دیگر همین زمان مقصد را پس ما دو عمل با زمان logn داریم دیگه
1- درخت دودویی کامل هست نه درخت جستجوی دودویی پس نمیشه در logn مبدا و یا مقصد را پیدا کرد.
2- اگر هم بشه شما میگی یکبار مبدا را پیدا کنیم در زمان logn و بار دیگر همین زمان مقصد را پس ما دو عمل با زمان logn داریم دیگه
20 دى 1390, 12:05 ق.ظ
(19 دى 1390 11:08 ب.ظ)pos نوشته شده توسط: [ -> ]قانع نشدم اخوی. دو تا مشکل دارم:
۱- درخت دودویی کامل هست نه درخت جستجوی دودویی پس نمیشه در logn مبدا و یا مقصد را پیدا کرد.
آخره سوال گفته میدانیم هر گره از این درخت به گره های فرزند و گره های پدر دسترسی دارد.
پس میتونه با مرتبه logn گره پدر رو پیدا کنه.
(19 دى 1390 11:08 ب.ظ)pos نوشته شده توسط: [ -> ]۲- اگر هم بشه شما میگی یکبار مبدا را پیدا کنیم در زمان logn و بار دیگر همین زمان مقصد را پس ما دو عمل با زمان logn داریم دیگه
نگاه کن به ازای هر بار که گره پدر رو به دست میاره باید مسیره گره های فرزندان اونو هم چک کنه. مستقیم نمیره سر ریشه.
20 دى 1390, 12:15 ق.ظ
ببخشید [tex]lg^{2}~n[/tex] میشه [tex]lg~lg~n[/tex] یا [tex]lg~n*lg~n[/tex] ؟؟
20 دى 1390, 12:27 ق.ظ
(20 دى 1390 12:15 ق.ظ)Ali-B نوشته شده توسط: [ -> ]ببخشید [tex]lg^{2}~n[/tex] میشه [tex]lg~lg~n[/tex] یا [tex]lg~n*lg~n[/tex] ؟؟
[tex]lg~n*lg~n[/tex]
20 دى 1390, 12:04 ب.ظ
(19 دى 1390 11:08 ب.ظ)pos نوشته شده توسط: [ -> ]قانع نشدم اخوی. دو تا مشکل دارم:
۱- درخت دودویی کامل هست نه درخت جستجوی دودویی پس نمیشه در logn مبدا و یا مقصد را پیدا کرد.
۲- اگر هم بشه شما میگی یکبار مبدا را پیدا کنیم در زمان logn و بار دیگر همین زمان مقصد را پس ما دو عمل با زمان logn داریم دیگه
به نظر پاسخ کامل بود
شکل پیاده سازیش اینجوریه که در یک حلقه For از یک تا logn یک حلقه For دیگه داریم از یک تا logn که در این دو حلقه تک تک مسیرها رو چک می کنیم.
ممکنه در همون ابتدا گره پیدا بشه ممکنه در انتها.
پس مرتبه زمانی( O(logn^2 می باشد
البته اگه استدلالم اشتباهه بگید
24 دى 1390, 12:16 ق.ظ
بدترین حالت اینه که یه درخت پر رو فرض کنیم. و از چپ ترین برگ رو به عنوان راس u و راست ترین برگ رو به عنوان راس v انتخاب کنیم.
دوستان من اینو حلش کردم ولی جواب رو log^3 n در آوردم.
توضیحات رو توی ضمیمه نوشتم ... بخونید ببینید کجاش غلطه
خب اینم یه راه حله دیگه...!
دوستان من اینو حلش کردم ولی جواب رو log^3 n در آوردم.
توضیحات رو توی ضمیمه نوشتم ... بخونید ببینید کجاش غلطه
خب اینم یه راه حله دیگه...!
30 دى 1390, 08:39 ب.ظ
جواب صحیح میشه گزینه ۴، طبق کتاب سنجش،،،
کتاب یوسفی هم در غلطنامه! صفحه آخر، گزینه صحیح نوشته.
کتاب یوسفی هم در غلطنامه! صفحه آخر، گزینه صحیح نوشته.