La gente da buenas respuestas en términos de notación big-O. De hecho, es [math] O (arraySize \ cdot sizeOfInt) [/ math] y [math] O (arraySize) [/ math]. El tamaño de int en C ++ está garantizado en al menos 16 bits. En la práctica, son 32 bits en plataformas Intel de 32 o 64 bits.
Sin embargo, es mucho más difícil obtener una respuesta en términos de ciclos de CPU reales por dos razones. Primero, por http://en.wikipedia.org/wiki/Branch_predictor. Los procesadores superescalares modernos pueden realizar más de una operación por ciclo de CPU. Sin embargo, una predicción errónea de una sola rama puede costarle 10-15 ciclos de CPU desperdiciados. No es necesario decir que el rendimiento real de muchos algoritmos depende mucho de la tasa de predicción errónea de la rama.
Con suerte, el predictor de bifurcación del bucle externo debe proporcionar una suposición correcta (b / c la mayor parte del tiempo, vuelve al comienzo del bucle).
- Tengo 23 años. ¿Es demasiado tarde para estudiar la introducción a algoritmos por CLRS?
- ¿Cuál es el número más pequeño [matemática] N [/ matemática] tal que [matemática] N \ equiv 2 \ mod 3, [/ matemática] [matemática] N \ equiv 1 \ mod 5, [/ matemática] [matemática] N \ equiv 4 \ mod 7 [/ matemáticas]?
- Para ubicarse dentro del top 3 en el próximo ICPC regional, ¿qué le sugeriría a un codificador de nivel medio que tenga suficiente conocimiento?
- ¿Hay alguna manera / hay algoritmos para dividir los caracteres chinos en radicales?
- Dada una lista de cadenas, ¿cómo puedo determinar si existe un orden de caracteres para el cual las cadenas están ordenadas en orden lexicográfico?
En segundo lugar, si sus enteros contienen solo unos pocos bits, el bucle interno terminará habitualmente antes en comparación con el caso de los enteros con muchos.
