En la "Estructura de datos" del profesor Yan Weimin, ¿cómo escribir la complejidad del tiempo, como logn, cuál es la base de esta función logarítmica?

La complejidad temporal a nivel de registro en el algoritmo se debe al uso de la idea de divide y vencerás, y esta base está determinada directamente por la complejidad de divide y vencerás. Si se utiliza la dicotomía, la base es 2, la base es 3, y así sucesivamente. Sin embargo, no importa cuál sea la base, el significado de progresión a nivel logarítmico es el mismo. En otras palabras, la complejidad temporal del algoritmo aumenta al mismo tiempo que se procesan los datos.

Datos extendidos:

Método de cálculo de la complejidad del tiempo

(1) En términos generales, el número de repeticiones de operaciones básicas en el algoritmo es función de la tamaño del problema n, representado por T(n). Si existe una función auxiliar f(n) tal que el valor límite de T(n)/f(n) es una constante distinta de cero (cuando n tiende a infinito), entonces f(n) se llama T(.< / p>

Supongamos que T(n)=O(f(n)) se llama O(f(n))

Es la complejidad temporal asintótica del algoritmo, denominada complejidad temporal.

(2) Al calcular la complejidad del tiempo, primero descubra la operación básica del algoritmo, luego determine el número de ejecuciones de acuerdo con la declaración correspondiente y luego encuentre el mismo orden de magnitud de T ( n).

(3) Es más fácil de entender en pascal. El método de cálculo simple es: mire cuántos bucles for hay. Si solo hay un bucle for, la complejidad del tiempo es O (. n), y el segundo es O (n ^ 2). Por analogía, si existe un método de bisección, es O (logn). Si el método de bisección se utiliza para anidar un bucle for, la complejidad del tiempo es O (). .

Enciclopedia Baidu: complejidad del tiempo