וכעת לאחר שקבלנו תשובה נכונה, מי יודע להסביר מדוע בכל זאת
מה שנכתב לעיל לא ממש נכון ולא סתם כך
אף אחד לא מתייחס לשיקולים כאלו בחישובי סיבוכיות(חוץ מאולי
באקדמיה) ולמעשה כשאני כותב תוכנית במחשב אני באופן עקבי
מתייחס לדברים כאלו כאילו הם בסיבוכיות O(n) ולא כפי שנכתב לעיל.

אבל למעשה אנו כמעט בכל מצב משתמשים במשתנים שלמים בגודל חסום,
ויש לנו פרימטיבים שמדפיסים אותם, כעקרון הדפסה של מספר
לוקחת O(logN) זמן אבל במקרים הפרקטיים שלנו N חסום(אבל מאוד גדול) אבל הלוגריתם בבסיס 10 יוצא משהוא מאוד מצומצם שאפשר
להתייחס עליו כאל קבוע, מה גם שיש פונקציות פרימיטיביות
שמטפלות בהדפסה כזאת.

אילו היינו משתמשים במשתנים שלמים בגודל שרירותי ובאמת משאיפים
את N לאינסוף, אזי הניתוח הראשוני היה נכון וסיבוכיות הזמן
הייתה באמת O(Nlog(N))

1. השאלה פשוט לא נכונה.
לאלגוריתם יש סיבוכיות ואין לו מהירות-ביצוע.
לתוכנה יש מהירות-ביצוע ואין לה סיבוכיות.

"סיבוכיות של תוכנה" הוא מונח מעוות ולא נכון.

2. הנה מימוש ל-PRINT שעובד בזמן קבוע:
אנחנו עובדים במצב של Double Buffering מסויים שבו יש לכתוב את כל הפיקסלים לבאגר ואז להחליף בין הבאפרים.
אם אנחנו עובדים ברזולוציה של rx X ry אז יש צורך ב-rx*ry "השמות" של פיסקלים לבאפר, או כתיבה של rx*ry*k בתים(כאשר K הוא גודל של רשומה/כל דבר אחר שמגדיר צבע).
לא משנה מה נכתוב למסך - אנחנו תמיד כותבים את *כל* המסך לבאפר - אותו זמן ביצוע.

באלגוריתם יש פעולות שנחשבות כאטומיות ויש שלא(בעיקר כתלות במודל),
וזאת אפילו אם בשפת תיכנות או פסדו קוד זה או אחר.
אם נחשוב על מכונת טורינג אין ספק שפלט של מספר לוקח LOG(N)
זמן(צריך לכתוב אותו בסרט הפלט)
וכשאני מדפיס לפלט סטנדרטי אני מדפיס לפלט סדרתי!

זה בהנחנה שה-N של דני יהיה מספר בעל 1041 ספרות(וזה במצב של 26 של 40 שורות/עמודות), אם נעבוד ברזולוציה של 1200X1600 אפשר להכניס הרבה יותר...

בוא ננסה שוב...
במצב אני הצעתי לוקח להדפיס כל מספר(עד גבול מסויים) הזןמ שלוקח לדחוץ rx*ry*k בתים לבאפר.
אם ניקח מספר בסכאלה הבאה זה יקח rx*ry*k*2, אם ניקח מספר בסכאלה הבאה זה יקח rx*ry*k*3.
אז בעצם הנוסחה לחשב בזמן הדפסה של מספר אצלי היא rx*ry*k*n, כאשר rx ו-ry מציינים את הרזולוציה(rxXry), המספר שמציין את גודל הבלוק שמגדיר צבע הוא k, ו-n הוא הסכאלה.

עבור אותו מספר הסכאלה יכולה להיות שונה, תלוי ברזולוציה.

בוא נניח שאני עובד ברזולוציה של 800X600, צריך 3 בתים כדי להגדיר צבע של פיקסל מסויים(בית אחד עבור כל צבע ב-RGB, מ-0 על 255).
סתם, בלי לבדוק, בוא נניח שאפשר להספיד מספר בעל 3000 ספרות במצב הזה על מסך אחד(באפר אחד), כדי להדפיס מספר בעל 3001-6000 ספרות יהיה צורך ב-שני מסכים, וכו'.

בוא נבדוק כמה זמן יקח להדפיס את המספר 1.23456 * 10^43:
המספר בעל 39 ספרות, אם אני לא טועה, כלומר הוא נכנס למסף אחד, כלומר מדיפיסם אותו באותו הזמן שמדפיסים את המספר 1.23 * 10^10, ובאותו הזמן שלוקח להדפיס את המספר 10^2999, נכון?
יופי.
אם מדובא על לוג עשרוני(חזקות עשר), אז התוצאות הן:
LOG(1.23456 * 10^43) = 43.091
LOG(1.23 * 10^10) = 10.089
LOG(10^2999) = 2999

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

אז אתה צודק, אם המסרפ מספיק גדול יקח יותר זמן להדפיס אותו...
אבל!
1. דני עושה בגרות של 5 יחידות.
אין לו מספרים בסדר גודל כזה, כי פסקל(שאני מניח שהוא עובד בה) טיפשה מלהתמודד עם מספרים כמו 10^2999...
2. יותר זמן, אבל לא LOG(N) - את זה הוכחתי כרגע.
אנא הסר את טענתך המטועה(לדעתי, כמובן, כמו שציינתי למעלה).
3. מדובר על יישום לכשהוא ב-PC כי דני(שעושה בגרות של 5 יחידות במחשבים) עובד על PC(או שאני לא מכיר מספיק בתי-ספר בארץ...).
4. עדיין אני צודק ואתה טועה בעניין ה"סיבוכיות של תוכנה" - אין דבר כזה.
5. עבור מספרים בסדר גודל "נורמלי", יספיק אפילו המוד הסטנדרטי של דוס כי יש שם 25 שורות X 80 עמודות(25*80=2000, 2000 ספרות מספיקות, לא?)

תיקון טעות:
ק עכשיו שמתי לב, ה-26 על 40 שכתבתי בהתחלה לא נכון, מדובר על 25 על 80 כמו שמצויין בסוף.
כמו כן, זה אומר שההערכה של 3000 ספרות שנתתי לרזולוציה של 800X600 אינה נכונה, ההערבה שלי היא כעת יותר בכיוון ה-10000 ספרות, כך שהסכאלה הראשונה עצומה וכל מספר "נורמלי", והרבה מספרים "לא נורמליים" יכנסו לבאפר הראשון
מה גם שאם המספר הוא 1.23456 * 10^43 אפשר(ואכן עושים כך) להדפיס 1.23456e+43, ולכן מספרים עצומים יכנסו לסכאלה הראושנה(אלא אם כן הם בחזקה שהיא עצמה ארוכה מ-1000 ומשהוא ספרות..., ואפילו אז אפשר לכתבו את המעריך שוב כחזקה...מספרים עצומים!!!

לסיכום:
ככל שאטני מתווכח עם יותר אנשים יורת פעמים של העניין הזה אני נהיה משוכני יותר ויותר שאני צודק ואילו אתה ו-liranr טועיפ טעויות רבות ומרובות(שביניהם להתעלם ממה שאמרתי למרות שזה נכון).

1. לא טענתי שאנחנו בויכוח.
רק אמרתי את דעתי על הנושא.

2. כמובן שקראתי את התגובות שלך.
אני נוהג לקרוא את כל האשכול לפני שאני מגיב.
העניין הוא שאתה טוען שמעשית לא מתחבים בעניין, אבל המצב הוא באמת כך וכך.
אני טוען שמעשית לא מתחשבים בעניין בגלל שהמצב *אני* כך וכך.

זה ההבדל בין הדעות שלנו.

להדפיס מספר בן מליון ספרות לוקח יותר זמן מלהדפיס מספר
בן ספרה אחת. בניתוח סיבוכיות מדברים על שאיפה לאינסוף
לכן 0.0001N^2 > 10000N
הזמן שלוקח להדפיס מספר בן N ספרות הוא אסמפטוטית בשאיפה לאינסוף
O(log(N))
ועל כן אלגוריתם שמדפיס את כל המספרים מ1 עד N יש לו סיבוכיות
O(N*log(N))
כל חישובי סיבוכיות הם כמובן תלויים בפלטפורמה, אבל קשה לי
לדמיין פלטפורמה בה הדפסה של מספר בגודל כרצוני תהיה פחות
מlog(N)

קודם כל, למיטב ידיעתי המספר הראושני הגדול ביותר שנמצא הינו בן 8 מיליארד ספרות(לא מיליונים:-)), אבל זה סתם משהוא נחמד...

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

לא הבנתי כלל את החיושבים שלך(אינסוף? איזה אינסוף?)
אתה יכול לפרט יותר?

בכל מקרה, אפילו אם תוכיח שזמן הריצה תלוי באורך המספר(ואני מסכים עם זה) זה לא אומר דבר על הסיבוכיות של האלגוריתם.

זמן ריצה של QuickSort כפתרון רקורסיבי ארוך הרבה יותר מהפתרון האיטרטיבי, אבל יש להם אותה הסיבוכיות...

בברכה...

1. "דני שעשה בגרות 5 יחידות במחשבים כתב תוכנית מאוד פשוטה
המדפיסה על המסך את כל המספרים מ1 עד N".
זה נקרא "מעשי" ולא "תיאורטי מתמטי".
הבנת?
דיון תיאורטי מתמטי מתחילים ב"נניח שהיה לנו אלגוריתם ש..."

2. אין שום צורך להגיב על שאר ההודעה שלך כי טענת הבסיס שלך נשמטה תחת רגליך...אבל אני אעשה לך טובה...

3. בלה בלה בלה.
לא הסברת למה האלגוריתם פועל ב-O(Log(N)).
אתה סוטה מהנושא...או אולי מתחמק?

4. טענות 1,3,5 - השאלה אינה תיאוטית כמו שהוכחתי למעלה.
אני מצפה לתשובה רצינית.

5. "טענה 2 - אף אחד לא אמר שזמן הריצה של פונקציית ההדפסה הוא (log(n.
רק אמרנו שהוא ((O(log(n. אם ההבדל לא ברור לך, קרא את ההגדרה לעיל"
לפונקציה לא יכולה להיות תכונה כמו ((O(log(n.
כי לפונקציה אין סיבוכיות.
הסברתי את זה כבר מספר פעמים.
אם *אתה* לא מבין לך ללמוד קצת(קצת הרבה...)!

6. סמנטיקה:
*אלגוריתם הוא מונח מופשט.
א"א להחזיק אלגוריתם ביד.

* מייצגים אלגוריתם ע"י פסוודו-קוד.
פסוודו-קוד מייצג אלגוריתם - יש לו סיבוכיות ואין לו זמן ריצה.

*לקןד פסקל אין סיבוכיות כי זה יישום.
ליישום יש זמן ריצה ולא סיבוכיות(בניגוד להפשטה).

7. טעית בכל דבר שאמרת עד עכשיו.

8. אתה טועה גם בשורה האחרונה שלך.
m = inf.
לכן אפילו אם הקלט הוא הגודל של n -> inf, עדיין כמות הפעלות תהיה קטנה מאינסוף...