سلام.
تو درج نود قبل از نود با آدرس مشخص y، لیست باید پیمایش بشه و مرتبه این عمل هم (O(n هستش. ولی تو درج نود بعد از نود با آدرس مشخص y ما لیست رو پیمایش نمیکنیم و مرتبه زمانیش هم متفاوته.
خب چه فرقی دارن این دو تا؟ مگه تو درج نود بعد از یه نود مشخص هم پیمایش لیست لازم نیست؟ اگه نیست پس چطور می فهمیم که نود y کجاست که بعد از اون نود جدید رو درج کنیم؟
ممنون میشم به سوالم جواب بدید.
(۱۱ آبان ۱۳۹۴ ۰۴:۲۱ ب.ظ)Aurora نوشته شده توسط: مرتبه زمانیش چیه؟(۱)Ѳ
سلام.وقتی میگه با آدرس مشخص ،خب یعنی جاش مشخصه دیگه و نیازی به پیمایش نداره!
خب حالا اگه بگه "در یک لیست پیوندی یک طرفه ،درج نود بعد از نود با آدرس مشخص y انجام گیرد"، خب حالا پس یعنی آدرس y رو داریم،پس با استفاده از y.next به راحتی میتونیم نود مورد نظر رو بعد y درج کنیم. که مرتبه زمانیش طبیعتا O(1) خواهد بود.چون نیاز به پیمایش لیست نداره.
ولی حالا اگه بگه "در یک لیست پیوندی یک طرفه ،درج نود قبل از نود با آدرس مشخص y انجام گیرد"،خب حالا پس یعنی باز آدرس y رو داریم،ولی باید توجه داشته باشیم که لیست ما که دو طرفه نیست که ما بتونیم با استفاده از y.previous به نود قبل y دسترسی داشته باشیم!!
پس مجبوریم از نود اول تا زمانیکه به نودی برسیم که next اون y باشه،پیمایش کنیم(که به نود قبل y برسیم).که در بدترین حالت مرتبه زمانیش به اندازه کل نود های لیست یعنی O(n) خواهد بود.
امیدوارم خوب توضیح داده باشم.
(۱۱ آبان ۱۳۹۴ ۰۵:۲۱ ب.ظ)IranianWizard نوشته شده توسط: سلام.وقتی میگه با آدرس مشخص ،خب یعنی جاش مشخصه دیگه و نیازی به پیمایش نداره!
خب حالا اگه بگه "در یک لیست پیوندی یک طرفه ،درج نود بعد از نود با آدرس مشخص y انجام گیرد"، خب حالا پس یعنی آدرس y رو داریم،پس با استفاده از y.next به راحتی میتونیم نود مورد نظر رو بعد y درج کنیم. که مرتبه زمانیش طبیعتا O(1) خواهد بود.چون نیاز به پیمایش لیست نداره.
ولی حالا اگه بگه "در یک لیست پیوندی یک طرفه ،درج نود قبل از نود با آدرس مشخص y انجام گیرد"،خب حالا پس یعنی باز آدرس y رو داریم،ولی باید توجه داشته باشیم که لیست ما که دو طرفه نیست که ما بتونیم با استفاده از y.previous به نود قبل y دسترسی داشته باشیم!!
پس مجبوریم از نود اول تا زمانیکه به نودی برسیم که next اون y باشه،پیمایش کنیم(که به نود قبل y برسیم).که در بدترین حالت مرتبه زمانیش به اندازه کل نود های لیست یعنی O(n) خواهد بود.
امیدوارم خوب توضیح داده باشم.
خیلی ممنونم ازتون.
خیلی عالی توضیح دادید. درسته من اصلا حواسم نبود به اینکه ما امکان بازگشت به نود قبلی رو نداریم و به همین خاطر باید لیست رو پیمایش کرد!
بازم ممنون.
(۱۱ آبان ۱۳۹۴ ۰۷:۴۷ ب.ظ)@s@kur نوشته شده توسط: خیلی ممنونم ازتون.خواهش می کنم
خیلی عالی توضیح دادید. درسته من اصلا حواسم نبود به اینکه ما امکان بازگشت به نود قبلی رو نداریم و به همین خاطر باید لیست رو پیمایش کرد!
بازم ممنون.