El tutorial o código que verás en este post es la resolución más rápida y válida que hallamos a esta inquietud o dilema.
Solución:
Esta pregunta se hace mucho (¿es una pregunta de tarea popular de CS o algo así?) y la respuesta es siempre la misma: no.
Piénsalo matemáticamente. A menos que el array está ordenado, no hay nada que “cortar por la mitad” para darle la log(n) comportamiento.
Lea los comentarios de la pregunta para una discusión más profunda (que de todos modos probablemente esté fuera del alcance de la pregunta).
Considere esto: sin visitar cada elemento, ¿cómo sabes que algún elemento que no has visitado no es más grande que el más grande que has encontrado hasta ahora?
No es posible hacer esto en O(log(N)). Está O(N) en el mejor/peor/promedio de los casos porque uno tendría que visitar cada artículo en el array para determinar si es el más grande o no. La matriz no está ordenada, lo que significa que no puede tomar atajos.
Incluso en el caso de la paralelización, esto no se puede hacer en O(N)porque gran-o a la notación no le importa cuántas CPU tiene uno o cuál es la frecuencia de cada CPU. Se hace abstracción de esto específicamente para dar un estado bruto del problema.
La paralelización puede despreciarse porque el tiempo dedicado a dividir un trabajo puede considerarse igual al tiempo de ejecución secuencial. Esto se debe a que las constantes no se tienen en cuenta. Los siguientes son todos iguales:
O(N) = O(Const * N) = O(N / Const) = O(N + Const) = O(N - Const)
Por otro lado, en la práctica, los algoritmos paralelos divide y vencerás pueden brindarte algunos beneficios de rendimiento, por lo que puede funcionar un poco más rápido. Afortunadamente, gran-o no se ocupa de este análisis de complejidad algorítmica de grano fino.