סיבוכיות זמן ריצה

אנונימי123

משתמש מקצוען
שלום אשמח לקבל את זמן הריצה של הקוד הבא:


(for(i=n;i>0;i=i-2
(for(j=2;j<i;j=j*j
(for(k=j;k>0;k=k/2
;++ count

תודה!!!
 

תא חזי

משתמש סופר מקצוען
עיצוב גרפי
עימוד ספרים
עריכה תורנית
שלום אשמח לקבל את זמן הריצה של הקוד הבא:


(for(i=n;i>0;i=i-2
(for(j=2;j<i;j=j*j
(for(k=j;k>0;k=k/2
;++ count

תודה!!!
לדעתי העניה,
קוד:
O(2^n)
כי כל פעם שמוסיפים לערך המוזן בלולאה העליונה, כל הלולאות מכפילות את הפלט שלהן - כי הן מבוססות (בלולאה השניה - על כפל, ובלולאה השלישית - על חילוק) ביחס ישיר ללולאה העליונה.
(אשמח אם מישהו/מישהי יוכיחו לי שאני טועה, ויסבירו למה)

אבל קודם כל נעשה סדר, לצורך העניין אכתוב מחדש את הלולאות המקוננות בג'אווהסקריפט, ואציב כמה משתנים לצורך הבדיקה (וגם פלט קונסולה, כדי שנראה בפועל מה קורה):
PHP:
var n = 5
var count =1;

var i;
for (i = n; i>0; i=i-2) {
  for (j=2; j<i; j=j*j) {
    for (k=j; k>0; k=k/2) {
        count++;
        console.log("i="+i+"; j="+j+"; k="+k+";");
        console.log("running"+count+"times");
    }
  }
}
אפשר לראות את הרצת הקוד במלואה בכלי המפתחים בדפדפן.
 

אנונימי123

משתמש מקצוען
דרך אגב... עדיף לבריץ בשפת c בגאווהסקריפט לא ממש עובד...
int i, j, k,n=5,count=0;
for (i = n; i > 0; i = i - 2) {
for (j = 2; j < i; j = j * j) {
for (k = j; k > 0; k = k / 2) {
count++;
cout<<"running " << count << " times";
}
}
}​
 

תא חזי

משתמש סופר מקצוען
עיצוב גרפי
עימוד ספרים
עריכה תורנית
דרך אגב... עדיף לבריץ בשפת c בגאווהסקריפט לא ממש עובד...
int i, j, k,n=5,count=0;
for (i = n; i > 0; i = i - 2) {
for (j = 2; j < i; j = j * j) {
for (k = j; k > 0; k = k / 2) {
count++;
cout<<"running " << count << " times";
}
}
}​
לא קריטי. לא אוהב C.
(למה אתם לא מכניסים את הקוד בין תגיות קוד של הפורום? זה נוראי להבין מה כתוב שם כשזה כמו טקסט)
 

אנונימי123

משתמש מקצוען
הסבר התוצאה: (O(nlogn
תובנה ראשונה- שלושת הלולאות תלויות זו בזו, ולכן צריכים למצוא את הסדרה שנוצרת מהלולאות.
נתחיל בשתי הלולאות הפנימיות:
שהם יוצרות ביחד סדרה הנדסית של (log2, log4, log16),(ע"י פירוק של (log(j )
ומציאת הגודל של סדרה הנדסית הוא:
ה- n הגדולה ביותר ז"א במקרה שלנו הוא: n
ואז ביחד עם הלולאה החיצונית נוצר סדרה חשבונית של:
....logn+logn-2+logn-4.
ו- =(!log(n
nlogn

מקווה שמובן לכולם....
בהצלחה!
:D
 

אנונימי123

משתמש מקצוען
סליחה טעיתי קצת...:(
משתי הלולאות הפנימיות לא יוצרים סדרה הנדסית אלא לוקחים את הlogj הכי גדול שנוצר בכל איטרציה.....
ז"א בפעם הראשונה logn ובפעם השניה logn-2.
ומזה נוצר סדרה חשבונית יחד עם הלולאה החיצונית:
(logn+1)*(n/2) לחלק ל-2 (נוסחה של סדרה חשבונית)
n/2= מספר האיטרציות של הלולאה החיצונית.
1= תחום הנמוך של הסדרה שנוצרה (log2)
logn= תחום הגבוה של הסדרה שנוצרה.
ולפי הנוסחה יוצא nlogn

אפשר גם לפי ההוכחה של !n:
....logn+logn-2+logn-4.
ו- =(!log(n
nlogn


מובן???
 

אולי מעניין אותך גם...

הפרק היומי

הפרק היומי! כל ערב פרק תהילים חדש. הצטרפו אלינו לקריאת תהילים משותפת!


תהילים פרק קיט ב'

ט בַּמֶּה יְזַכֶּה נַּעַר אֶת אָרְחוֹ לִשְׁמֹר כִּדְבָרֶךָ:י בְּכָל לִבִּי דְרַשְׁתִּיךָ אַל תַּשְׁגֵּנִי מִמִּצְוֹתֶיךָ:יא בְּלִבִּי צָפַנְתִּי אִמְרָתֶךָ לְמַעַן לֹא אֶחֱטָא לָךְ:יב בָּרוּךְ אַתָּה יְהוָה לַמְּדֵנִי חֻקֶּיךָ:יג בִּשְׂפָתַי סִפַּרְתִּי כֹּל מִשְׁפְּטֵי פִיךָ:יד בְּדֶרֶךְ עֵדְוֹתֶיךָ שַׂשְׂתִּי כְּעַל כָּל הוֹן:טו בְּפִקֻּדֶיךָ אָשִׂיחָה וְאַבִּיטָה אֹרְחֹתֶיךָ:טז בְּחֻקֹּתֶיךָ אֶשְׁתַּעֲשָׁע לֹא אֶשְׁכַּח דְּבָרֶךָ:
נקרא  9  פעמים

לוח מודעות

למעלה