0votos

A surpassing problem en JavaScript

por josejuan hace 6 años

Se pide comparar la eficiencia del algoritmo propuesto con otro O(n log n). Existe una versión con constante pequeña que es O(n), aquí pongo sólo el algoritmo O(n) trivial (con constante "no pequeña").

JAlonso tuiteó un libro que contiene una serie de problemas. En él se presenta un problema que se resuelve con coste O(n log n). El desafío consiste en encontrar una solución con coste O(n) y ver porqué en la práctica NO ES más eficiente.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
function MaxSurpassingCount(s) { 
    var m = 0, l = s.length; 
    // Para cada elemento del conjunto C 
    for(var i = 65; i < 91; i++) { 
        // Buscamos primera aparición en S 
        var c = 0, w = String.fromCharCode(i), j = s.indexOf(w); 
        if(j >= 0) { 
            // Contamos surpassins 
            while(++j < l) if(s[j] > w) c++; 
            // Agregamos MAX 
            if(m < c) m = c; 
    return m; 
 
/* 
    El coste del algoritmo es O(n * m) donde 'n' es el tamaño de S y 'm' el de C. 
    El algoritmo es lineal porque 'm' es constante una vez fijado el problema. 
    Como es 
        n log n = m n 
        log n = m 
        n = e^m 
 
    Entonces, este algoritmo lineal será mejor opción cuando n > e^m 
    Para las letras indicadas A..Z tenemos que m = 26, por tanto la mejor estrategia es usar: 
        O(n log n) cuando n <= 2^26 = 67.108.864 
        O(n m) cuando n > 2^26 = 67.108.864 
    Para conjuntos más grandes (eg. números enteros representados con 32 bits) en la práctica nunca es más eficiente esta versión lineal pues 'n' debería ser mayor que 2^2^32 ~= 10^1292913986. 
 
    Sin embargo, existe otra versión lineal con coste (a ojo, luego puede diferir algo) 
 
        O(n + min(n, m)) 
 
    Que en la práctica es lineal ¿os animáis? 
*/ 

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.