۰
subtitle
ارسال: #۱
درج نود جدید در لیست پیوندی یک طرفه
سلام.
تو درج نود قبل از نود با آدرس مشخص y، لیست باید پیمایش بشه و مرتبه این عمل هم (O(n هستش. ولی تو درج نود بعد از نود با آدرس مشخص y ما لیست رو پیمایش نمیکنیم و مرتبه زمانیش هم متفاوته.
خب چه فرقی دارن این دو تا؟ مگه تو درج نود بعد از یه نود مشخص هم پیمایش لیست لازم نیست؟ اگه نیست پس چطور می فهمیم که نود y کجاست که بعد از اون نود جدید رو درج کنیم؟
ممنون میشم به سوالم جواب بدید.
تو درج نود قبل از نود با آدرس مشخص y، لیست باید پیمایش بشه و مرتبه این عمل هم (O(n هستش. ولی تو درج نود بعد از نود با آدرس مشخص y ما لیست رو پیمایش نمیکنیم و مرتبه زمانیش هم متفاوته.
خب چه فرقی دارن این دو تا؟ مگه تو درج نود بعد از یه نود مشخص هم پیمایش لیست لازم نیست؟ اگه نیست پس چطور می فهمیم که نود y کجاست که بعد از اون نود جدید رو درج کنیم؟
ممنون میشم به سوالم جواب بدید.
۲
ارسال: #۲
RE: درج نود جدید در لیست پیوندی یک طرفه
سلام.وقتی میگه با آدرس مشخص ،خب یعنی جاش مشخصه دیگه و نیازی به پیمایش نداره!
خب حالا اگه بگه "در یک لیست پیوندی یک طرفه ،درج نود بعد از نود با آدرس مشخص y انجام گیرد"، خب حالا پس یعنی آدرس y رو داریم،پس با استفاده از y.next به راحتی میتونیم نود مورد نظر رو بعد y درج کنیم. که مرتبه زمانیش طبیعتا O(1) خواهد بود.چون نیاز به پیمایش لیست نداره.
ولی حالا اگه بگه "در یک لیست پیوندی یک طرفه ،درج نود قبل از نود با آدرس مشخص y انجام گیرد"،خب حالا پس یعنی باز آدرس y رو داریم،ولی باید توجه داشته باشیم که لیست ما که دو طرفه نیست که ما بتونیم با استفاده از y.previous به نود قبل y دسترسی داشته باشیم!!
پس مجبوریم از نود اول تا زمانیکه به نودی برسیم که next اون y باشه،پیمایش کنیم(که به نود قبل y برسیم).که در بدترین حالت مرتبه زمانیش به اندازه کل نود های لیست یعنی O(n) خواهد بود.
امیدوارم خوب توضیح داده باشم.
خب حالا اگه بگه "در یک لیست پیوندی یک طرفه ،درج نود بعد از نود با آدرس مشخص y انجام گیرد"، خب حالا پس یعنی آدرس y رو داریم،پس با استفاده از y.next به راحتی میتونیم نود مورد نظر رو بعد y درج کنیم. که مرتبه زمانیش طبیعتا O(1) خواهد بود.چون نیاز به پیمایش لیست نداره.
ولی حالا اگه بگه "در یک لیست پیوندی یک طرفه ،درج نود قبل از نود با آدرس مشخص y انجام گیرد"،خب حالا پس یعنی باز آدرس y رو داریم،ولی باید توجه داشته باشیم که لیست ما که دو طرفه نیست که ما بتونیم با استفاده از y.previous به نود قبل y دسترسی داشته باشیم!!
پس مجبوریم از نود اول تا زمانیکه به نودی برسیم که next اون y باشه،پیمایش کنیم(که به نود قبل y برسیم).که در بدترین حالت مرتبه زمانیش به اندازه کل نود های لیست یعنی O(n) خواهد بود.
امیدوارم خوب توضیح داده باشم.
ارسال: #۳
RE: درج نود جدید در لیست پیوندی یک طرفه
(۱۱ آبان ۱۳۹۴ ۰۵:۲۱ ب.ظ)IranianWizard نوشته شده توسط: سلام.وقتی میگه با آدرس مشخص ،خب یعنی جاش مشخصه دیگه و نیازی به پیمایش نداره!
خب حالا اگه بگه "در یک لیست پیوندی یک طرفه ،درج نود بعد از نود با آدرس مشخص y انجام گیرد"، خب حالا پس یعنی آدرس y رو داریم،پس با استفاده از y.next به راحتی میتونیم نود مورد نظر رو بعد y درج کنیم. که مرتبه زمانیش طبیعتا O(1) خواهد بود.چون نیاز به پیمایش لیست نداره.
ولی حالا اگه بگه "در یک لیست پیوندی یک طرفه ،درج نود قبل از نود با آدرس مشخص y انجام گیرد"،خب حالا پس یعنی باز آدرس y رو داریم،ولی باید توجه داشته باشیم که لیست ما که دو طرفه نیست که ما بتونیم با استفاده از y.previous به نود قبل y دسترسی داشته باشیم!!
پس مجبوریم از نود اول تا زمانیکه به نودی برسیم که next اون y باشه،پیمایش کنیم(که به نود قبل y برسیم).که در بدترین حالت مرتبه زمانیش به اندازه کل نود های لیست یعنی O(n) خواهد بود.
امیدوارم خوب توضیح داده باشم.
خیلی ممنونم ازتون.
خیلی عالی توضیح دادید. درسته من اصلا حواسم نبود به اینکه ما امکان بازگشت به نود قبلی رو نداریم و به همین خاطر باید لیست رو پیمایش کرد!
بازم ممنون.
ارسال: #۴
RE: درج نود جدید در لیست پیوندی یک طرفه
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close