Análisis de Algoritmos | Conjunto 2 (peor, promedio y mejores casos)

En la publicación anterior , discutimos cómo el análisis asintótico supera los problemas de la forma ingenua de analizar algoritmos. En esta publicación, tomaremos un ejemplo de búsqueda lineal y lo analizaremos utilizando el análisis asintótico.
Podemos tener tres casos para analizar un algoritmo: 
1) El peor caso 
2) El caso promedio 
3) El mejor caso

Ejemplo 1:
Consideremos la siguiente implementación de Búsqueda lineal. 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
// Linearly search x in arr[].
// If x is present then return the index,
// otherwise return -1
int search(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++) {
        if (arr[i] == x)
            return i;
    }
    return -1;
}
  
// Driver Code
int main()
{
    int arr[] = { 1, 10, 30, 15 };
    int x = 30;
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << x << " is present at index "
         << search(arr, n, x);
  
    getchar();
    return 0;
}
  
// This code is contributed
// by Akanksha Rai

// C implementation of the approach
#include <stdio.h>
  
// Linearly search x in arr[].
// If x is present then return the index,
// otherwise return -1
int search(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++) {
        if (arr[i] == x)
            return i;
    }
    return -1;
}
  
/* Driver program to test above functions*/
int main()
{
    int arr[] = { 1, 10, 30, 15 };
    int x = 30;
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d is present at index %d", x,
           search(arr, n, x));
  
    getchar();
    return 0;
}

// Java implementation of the approach
  
public class GFG {
  
    // Linearly search x in arr[].  If x is present then
    // return the index, otherwise return -1
    static int search(int arr[], int n, int x)
    {
        int i;
        for (i = 0; i < n; i++) {
            if (arr[i] == x) {
                return i;
            }
        }
        return -1;
    }
  
    /* Driver program to test above functions*/
    public static void main(String[] args)
    {
        int arr[] = { 1, 10, 30, 15 };
        int x = 30;
        int n = arr.length;
        System.out.printf("%d is present at index %d", x,
                          search(arr, n, x));
    }
}
  
/*This code is contributed by PrinciRaj1992*/

# Python 3 implementation of the approach
  
# Linearly search x in arr[]. If x is present
# then return the index, otherwise return -1
  
  
def search(arr, x):
    for index, value in enumerate(arr):
        if value == x:
            return index
    return -1
  
  
# Driver Code
arr = [1, 10, 30, 15]
x = 30
print(x, "is present at index",
      search(arr, x))
  
# This code is contributed
# by PrinciRaj1992

// C# implementation of the approach
using System;
public class GFG {
  
    // Linearly search x in arr[].  If x is present then
    // return the index, otherwise return -1
    static int search(int[] arr, int n, int x)
    {
        int i;
        for (i = 0; i < n; i++) {
            if (arr[i] == x) {
                return i;
            }
        }
        return -1;
    }
  
    /* Driver program to test above functions*/
    public static void Main()
    {
        int[] arr = { 1, 10, 30, 15 };
        int x = 30;
        int n = arr.Length;
        Console.WriteLine(x + " is present at index "
                          + search(arr, n, x));
    }
}
  
/*This code is contributed by PrinciRaj1992*/

<?php
// PHP implementation of the approach
  
// Linearly search x in arr[]. If x 
// is present then return the index,
// otherwise return -1
function search($arr, $n, $x)
{
    for ($i = 0; $i < $n; $i++)
    {
    if ($arr[$i] == $x)
        return $i;
    }
    return -1;
}
  
// Driver Code
$arr = array(1, 10, 30, 15);
$x = 30;
$n = sizeof($arr);
echo $x . " is present at index ". 
             search($arr, $n, $x);
  
// This code is contributed 
// by Akanksha Rai

<script>
// javascript implementation of the approach
  
     // Linearly search x in arr. If x is present then
    // return the index, otherwise return -1
    function search(arr , n , x) {
        var i;
        for (i = 0; i < n; i++) {
            if (arr[i] == x) {
                return i;
            }
        }
        return -1;
    }
  
    /* Driver program to test above functions */
      
        var arr = [ 1, 10, 30, 15 ];
        var x = 30;
        var n = arr.length;
        document.write(x+" is present at index "+ search(arr, n, x));
  
// This code is contributed by gauravrajput1 
</script>

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
int getSum(int arr[] , int n)
{
    if(n%2==0) // (n) is even
    {
        return 0;
    }
    int sum=0;
    for (int i = 0; i < n; i++)
    {
        sum+=arr[i];
    }
    return sum; //  (n) is odd
}
  
// Driver Code
int main()
{
    // Declaring two array one of length odd and other of length even;
    int arr[4]={1,2,3,4};
    int a[5] ={1,2,3,4,5};
    cout<<getSum(arr,4)<<endl;// print 0 because (n) is even
    cout<<getSum(a,5)<<endl; // print sum because (n) is odd
}
// This code is contributed by Suruchi Kumari

#include <stdio.h>
  
int getSum(int arr[] , int n)
{
    if(n%2==0) // (n) is even
    {
        return 0;
    }
    int sum=0;
    for (int i = 0; i < n; i++)
    {
        sum+=arr[i];
    }
    return sum; //  (n) is odd
}
  
// Driver Code
int main()
{
    // Declaring two array one of length odd and other of length even;
    int arr[4]={1,2,3,4};
    int a[5] ={1,2,3,4,5};
    printf("%d\n",getSum(arr,4));// print 0 because (n) is even
    printf("%d\n",getSum(a,5)); // print sum because (n) is odd
}
// This code is contributed by Suruchi Kumari