שאלה כללית לגבי סיבוכיות

[patch81]

שאלה כללית לגבי סיבוכיות

נניח שיש לי אלגוריתם עם שני שלבים כל שלב לוקח lg האם החסם באסימפטוטי של האלגוריתם הוא O(lgn) או log + lg = lg(n^2) הרי אם זה היה n הייתי מקבל n+n= 2n= O אבל מה קורה במקרה של הלוגריתם ? תודה

 

[JohnnyPiloni]

זה אותו הדבר כמו (n+n= 2n= O(n

(logn+logn= 2logn = O(logn

 

[patch81]

כן אבל

הרי log + log = log(n*n) = log(n^2) לא ?

 

[vinney]

שזה 2logn

אז מה בדיוק הבעיה?

 

[patch81]

כן. אבל מה שזה אומר

זה שלמעשה log זהה אסימפטוטית ל log(n^2) כלומר שהסיבוכיות של עץ בינארי עם n איברים זהה לסיבוכיות עם n^2 איברים. לכן זה לא מסתדר לי

 

[vinney]

זה לא זהה אסימפטוטית

זה זהה, נקודה. log n^2 = 2log n לגבי סיבוכיות, זה כבר משהו אחר. סיבוכיות אכן נמדדת במושגים אסימפטוטיים, והסיבוכיות של עץ בגודל n ובגודל n^2 אכן לא זהה, אבל מאותו סדר גודל. מה זה אומר? שהחסמים הם אותם החסמים (log n בהתעלם מהמקדמים). אני מקווה שזה לא חדש לך

 

[vicz]

אתה מתבלבל

בין לוג' בריבוע של n שזה: lgn*lgn לבין לוג' של n בריבוע שזה: lg(n^2) ובין השאר גם lgn+lgn=lg(n^2). לפי חוקי לוגוריתמים:

lg(n^m)=mlgn​