מה הסיבוכיות?

[JohnnyPiloni]

מה הסיבוכיות?

1.

for (i=0; i < n; i *=4) { }​

2.

for (i=0; i < N; i *=4) { }​

N שווה לn ברביעית

 

[vinney]

אפשר לשאול מאיפה השאלה?

 

[Okuryo]

../images/Emo119.gifזו לולאה אינסופית...

אם n>0. [כי 0=4*0.] אם n<0, תהיה חזרה אחת בדיוק.

 

[vinney]

(לא שמת לב לN)

(שהוא n ברביעית) (אם n שלילי, אז הלולאה הראשונה עוצרת, השנייה - לעולם לא) (שאלה מפגרת לדעתי)

 

[JohnnyPiloni]

אני אתקן i שוה ל 1 ולא ל 0

 

[Okuryo]

../images/Emo119.gifאם כך,

Θ( log_4 ) = Θ(lg n)​

לשניהם.

 

[vinney]

מה שהוא אמר

(יצאתי

, לא שמתי לב לכפול) בכל מקרה, מאיפה השאלה הזאת?

 

[Okuryo]

../images/Emo119.gifאבל אתה יכול למחוק הודעות שלך ../images/Emo6.gif

 

[vinney]

נכון../images/Emo13.gif

אני יכול למחוק הודעות גם של אחרים

 

[JohnnyPiloni]

השאלה!

חשבתי על משהו שאפשר לעשות במערך (לרוץ מתחילת המערך בקפיצות של חזקה) בגלל זה השאלה קצת מוזרה בכל מקרה אם עושים קפיצות של כפולות של 4 הסיבוכיות היא logn עם בסיס 4 ? ואם עושים קפיצות של 2, 4, 8, וכו' הסיבוכיות היא logn עם בסיס 2 ?

 

[Okuryo]

../images/Emo119.gifאכן.

ובסדר הגודל כל הלוגים זהים, כי הם נבדלים פי קבוע.