שאלה במבני נתונים
חברכם טוען שמצא אלגוריתם חיפוש במערך ממוין בסיבוכיות שורש-לוגריתמית. כלומר, בהינתן מערך ממוין Values כלשהו שארכו n, האלגוריתם יכול למוצא האם v כלשהו נמצא בValues בזמן O(√log
). לטענת חברכם, האלגוריתם פועל לכל מערך כלשהו (לאו דווקא של מספרים שלמים, לדוגמה); כל שנדרש הוא שאפשר להשוות בין שני איברים בΘ(1). יש גם רמז: כל מיון מבוסס השוואות פועל ב T=nlogn הכוונה לאומגה של nlogn.
חברכם טוען שמצא אלגוריתם חיפוש במערך ממוין בסיבוכיות שורש-לוגריתמית. כלומר, בהינתן מערך ממוין Values כלשהו שארכו n, האלגוריתם יכול למוצא האם v כלשהו נמצא בValues בזמן O(√log
). לטענת חברכם, האלגוריתם פועל לכל מערך כלשהו (לאו דווקא של מספרים שלמים, לדוגמה); כל שנדרש הוא שאפשר להשוות בין שני איברים בΘ(1). יש גם רמז: כל מיון מבוסס השוואות פועל ב T=nlogn הכוונה לאומגה של nlogn.