Pregunta

The following question was:

What is the Big O complexity of your algorithm in part? Explain your answer and describe the number of operations that take place in the worst case.

I haven't yet quite gotten to that -you don't have to answer it if you don't want but again, I will greatly appreciate your help and will help me to learn through some exemplar answers. Thank you :)

Again! this is not a question in relation to homework and such.. I'm trying to solve some answers (I usually do in my spare time) and I know people here are much better at teaching than my tutors (who hardly speaks English). Thank you everyone.

¿Fue útil?

Solución

bool IsHaveDup(int[] myArray, int arraySize)
{
    int i, j;
    bool isHaveDup = false;

    for (i = 0; i < arraySize - 1; i++)
    {
        for (j = i + 1; j < arraySize; j++)
        {
            if (myArray[i] == myArray[j])
            {
                isHaveDup = true;
                break;
            }
        }

        if (isHaveDup)
        {
            break;
        } 
    }

    return isHaveDup;
}

The complexity is O(N^2) = N * ((N + 1)/2)

A better solution is to sort the array and then check for duplication then complexity is O(N*logN) for sorting and one quick loop on the array for duplication O(N) In total: O(N)+O(n*logN) = O(NlogN)

Otros consejos

JS exanoke?

<!DOCTYPE HTML>
<html>
    <head>
        <title>Bla!</title>
        <style type='text/css'>
        </style>
        <script type='text/javascript'>
            var m_Array = [1,3,7,3,8,23,33,11,1,8,9,10,32,44,156,4,2,8,1];

            function CompairArray(f_Array) {
                for (var i in f_Array) {
                    for (var j =0; j<i; j++) {
                        if (f_Array[i] == f_Array[j]) {
                            alert ("index " + j + " same as index " + i + " and is " +f_Array[j]);
                        }
                    }
                }
            }

            function Init() {
                CompairArray(m_Array);
            }
        </script>
    </head>
    <body class='body' onload='Init();'>

    </body>
</html>
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top