<jupyter_start><jupyter_text>TD7  Comparaison de deux algorithmes de recherche<jupyter_code>public int cherche1(int[] tab, int x) {
    int sol = -1;
    for (int i = 0; i < tab.length; i++) {
        if (tab[i] == x) {
            sol = i;
        }
    }
    return sol;
}
public int cherche2(int[] tab, int x) {
    for (int i = 0; i < tab.length; i++) {
        if (tab[i] == x) {
            return i;
        }
    }
    return -1;
}
int[] tab = new int[] { 5, 4, 7, 8, 1 };
System.out.println("cherche1: " + cherche1(tab, 7));
System.out.println("cherche2: " + cherche2(tab, 7));<jupyter_output><empty_output><jupyter_text>Mais lequel est le plus « efficace » ?<jupyter_code>public int cherche1(int[] tab, int x) {
    int sol = -1;
    for (int i = 0; i < tab.length; i++) {
        System.out.println(i);
        if (tab[i] == x) {
            sol = i;
        }
    }
    return sol;
}
public int cherche2(int[] tab, int x) {
    for (int i = 0; i < tab.length; i++) {
        System.out.println(i);
        if (tab[i] == x) {
            return i;
        }
    }
    return -1;
}
int[] tab = new int[] { 5, 4, 7, 8, 1 };
System.out.println("cherche1: " + cherche1(tab, 7));
System.out.println("cherche2: " + cherche2(tab, 7));<jupyter_output><empty_output><jupyter_text>Ne pas confondre ce qu'on calcule avec la complexité du calcul<jupyter_code>int factorielle(int n) {
    int complexite = 0;
    int i = n;
    int res = 1;
    while (i > 0) {
        res = res*i;
        i--;
        complexite += 2;
    }
    System.out.println("complexite factorielle : " + complexite);
    return res;
}

System.out.println(factorielle(5));
int puissance(int x, int n) {
    int complexite = 0;
    int i = n;
    int res = 1;
    while (i > 0) {
        res = res*x;
        i--;
        complexite += 2;
    }
    System.out.println("complexite puissance : " + complexite);
    return res;
}

System.out.println(puissance(2, 5));<jupyter_output><empty_output><jupyter_text>Comment calculer la complexité ?<jupyter_code>public int[] calcul(int[] tab1, int[] tab2) {
    int complexite = 0;
    int[]  tab3 = new int[tab1.length];
    for (int i = 0; i < tab1.length; i++) {
        if (tab1[i] < tab2[i]) {
            tab3[i] = factorielle(tab1[i]);
            complexite += 1;
        } else {
            tab3[i] = i;
            complexite += 1;
        }
    }
    System.out.println("complexite calcul : " + complexite);
    return tab3;
}<jupyter_output><empty_output><jupyter_text>Complexité au pire<jupyter_code>int[] tab1 = new int[] { 2, 3, 4 };
int[] tab2 = new int[] { 5, 5, 5 };
System.out.println(Arrays.toString(calcul(tab1, tab2)));<jupyter_output><empty_output><jupyter_text>Complexité au mieux<jupyter_code>int[] tab1 = new int[] { 5, 6, 7 };
int[] tab2 = new int[] { 5, 5, 5 };
System.out.println(Arrays.toString(calcul(tab1, tab2)));<jupyter_output><empty_output><jupyter_text>Exercice : donner la complexité au pire de l'algorithme suivant<jupyter_code>int m = 5;
int n = 4;
int p = 6;
int[][] matM = new int[m][n];
int[][] matN = new int[n][p];
int[][] matP = new int[m][p];

for (int i = 0; i < m; i++) {
    for (int j = 0; j < p; j++) {
        matP[i][j] = 0;
        for (int k = 0; k < n; k++) {
            matP[i][j] = matP[i][j] + matM[i][k] * matN[k][j];
        }
    }
}<jupyter_output><empty_output><jupyter_text>Pourquoi trier ?<jupyter_code>boolean recherche(int v, int[] tab) {
    int complexite = 0;
    for (int i = 0 ; i < tab.length ; i++) {
        complexite++;
        if (tab[i] == v) {
            System.out.println("complexite recherche : " + complexite);
            return true;
        }
    }
    System.out.println("complexite recherche : " + complexite);
    return false;
}
boolean rechercheDichotomique(int v, int[] tab, int deb, int fin) {
    System.out.println("complexite rechercheDichotomique");
    if (deb == fin) {
        if (tab[deb] == v) { return true;  }
        else { return false; }
    } else {
        int k = (deb + fin) / 2; // on coupe en 2 l'espace de recherche
        if (tab[k] < v) { return rechercheDichotomique(v, tab, k + 1, fin); }
        else { return rechercheDichotomique(v, tab, deb, k); }
    }
}

boolean rechercheDichotomique(int v, int[] tab) {
    return rechercheDichotomique(v, tab, 0, tab.length - 1);
}
int[] tab = new int[] { 5, 4, 7, 8, 1, 2, 3, 6, 9, 10 };
System.out.println(recherche(10, tab));
int[] tab = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
System.out.println(rechercheDichotomique(10, tab));<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1691224983505608, 'fraction_numerical': 0.026610952276226084, 'mean_word_length': 2.63258785942492, 'pattern_counts': {'":': 0, '<': 44, '<?xml version=': 0, '>': 35, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '135892', 'license': 'MIT', 'n_tokens_mistral': 1837, 'n_tokens_neox': 1741, 'n_words': 449, 'path': 'notebooks/TD7.ipynb', 'repo_name': 'Skymirrh/Java2STPI', 'size': '4547'}