קצת על סיבוכיות

כשסיבוכיות באה לידי מעשה

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

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


ובפשטות, ממשו את הפונקציה findMissingNumber:

    public static void main(String[] args) {
        // N is 6
        int[] array = new int[] {0, 1, 2, 6, 4, 3};
        
        int missingNumber = findMissingNumber(array);
        System.out.println("The missing number is: " + missingNumber); // 5
    }

דרך א:
נבדוק עבור כל מספר מ-0 עד N האם הוא קיים במערך.
הסיבוכיות של דרך זו היא n בריבוע.

    
    private static int findMissingNumber(int[] array) {
        for (int searchedNum = 0; searchedNum <= array.length; searchedNum++) {
            boolean searchedNumFound = false;
            
            for (int currNum : array) {
                if (currNum == searchedNum) {
                    searchedNumFound = true;
                    break;
                }
            }
            
            if (!searchedNumFound) {
                return searchedNum;
            }
        }
        
        return -1;
    }

דרך ב:
נמיין את המערך ואז נבדוק מתי תא מכיל ערך שאינו האינדקס שלו. אם הערך החסר היה N פשוט נחזיר את האינדקס האחרון + 1.
הסיבוכיות של דרך זו היא ((n) + (n log(n).

    private static int findMissingNumber(int[] array) {
        int index;
        Arrays.sort(array); // O(n log(n))
        
        for (index = 0; index < array.length; index++) {
            if (array[index] != index) {
                break;
            }
        }
        
        return index;
    }

דרך ג:
נסמן במערך בוליאני כל מספר שנמצא, ואז נבדוק איזה מספר לא סומן במערך.
הסיבוכיות של דרך זו היא 2n.

    private static int findMissingNumber(int[] array) {
        
        // Init the array to default false values
        boolean[] existingNumbers = new boolean[array.length + 1];
        
        for (int currNum : array) {
            existingNumbers[currNum] = true;
        }
        
        for (int searchedNum = 0; searchedNum < existingNumbers.length; searchedNum++) {
            if (!existingNumbers[searchedNum]) {
                return searchedNum;
            }
        }
        
        return -1;
    }

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

    private static int findMissingNumber4(int[] array) {
        int N = array.length;
        
        // Sum of arithmetic progression
        // 0, 1, 2, 3, ..., N
        int sumOfAllNumbers = (N * (N + 1)) / 2;
        int sumOfExistingNumbers = 0;
        
        for (int currNum : array) {
            sumOfExistingNumbers += currNum;
        }
        
        return sumOfAllNumbers - sumOfExistingNumbers;
    }

בהצלחה.