graph - sheet - Notación Big O con valor absoluto?

insertion sort complexity

Question

Estoy repasando algunos libros de preguntas sobre entrevistas de programación, y he visto referencias a la complejidad del tiempo "O(|A|)" . Nunca he visto esta notación con el valor absoluto dado.

Algunas investigaciones me llevaron a Big O Cheatsheet que hace referencia a esta notación en la sección de gráficos. El problema que estoy investigando es sobre la partición de una matriz, que en realidad no es una pregunta gráfica (aunque me arriesgaría quizás a mostrar mi ignorancia con esa afirmación).

Hace |A| refiérase a la magnitud de la matriz, o de lo contrario el número de elementos, es decir, O(N) ?

Answer 1

En la notación de teoría de conjuntos |A| es la cardinalidad del conjunto A , en otras palabras, la cantidad de elementos contenidos en el conjunto A

Para referencia: http://www.mathsisfun.com/sets/symbols.html

Answer 2

Verá esta notación siempre cuando A no es un número.

A podría ser muchas cosas, entonces |A| depende del contexto. P.ej

• A es un vector de un enrejado, entonces |A| es la longitud del vector.
• A es un algoritmo (tal vez desconocido) (por ejemplo, un atacante a un cifrado), luego |A| podría ser la complejidad de este algoritmo o la longitud del vector de bits aleatorios que utiliza este algoritmo.
• A es un conjunto, entonces es |A| la cantidad de elementos en el conjunto, como mencionó Kostub Deshmukh.

Puede haber muchos más casos.