Como podemos assumir que operações básicas sobre números levam tempo constante?

Normalmente, em algoritmos, não nos preocupamos com comparação, adição ou subtração de números - assumimos que eles correm no tempo . Por exemplo, assumimos isso quando dizemos que a classificação baseada em comparação é O ( n log n ) , mas quando os números são grandes demais para caber nos registros, normalmente os representamos como matrizes, para que operações básicas exijam cálculos extras por elemento.$O(1)$$O(n\log n)$

Existe uma prova mostrando que a comparação de dois números (ou outras funções aritméticas primitivas) pode ser feita em ? Se não, por que estamos dizendo que a classificação baseada em comparação é O ( n log n ) ?$O(1)$$O(n\log n)$

Eu encontrei este problema quando eu respondi a uma pergunta SO e eu percebi que o meu algoritmo não é , porque mais cedo ou mais tarde eu deveria lidar com big-int, também não era algoritmo de tempo pseudo polinomial, foi P .$O(n)$$P$

Para pessoas como eu que estudam algoritmos para sobreviver, o modelo padrão de computação do século XXI é a RAM inteira . O modelo pretende refletir o comportamento de computadores reais com mais precisão do que o modelo da máquina de Turing. Computadores do mundo real processam números inteiros de vários bits em tempo constante usando hardware paralelo; não números inteiros arbitrários , mas (como os tamanhos das palavras crescem constantemente ao longo do tempo) também não números inteiros de tamanho fixo .

$w$$w$$n$$O(1)$

Formalmente, o tamanho da palavra NÃO é uma constante$w$ para fins de análise de algoritmos nesse modelo. Para tornar o modelo consistente com a intuição, exigimos , pois, caso contrário, não podemos nem armazenar o número inteiro n em uma única palavra. No entanto, para a maioria dos algoritmos não numéricos, o tempo de execução é realmente independente de w , porque esses algoritmos não se importam com a representação binária subjacente de sua entrada. O mergesort e o heapsort são executados no tempo O ( n log n ) ; média de 3 corridas rápidas em O ( n $w \ge \log_2 n$$n$$w$$O(n\log n)$ no pior dos casos. Uma excepção notável é tipo Radix binário, o qual corre em S ( n w ) tempo.$O(n^2)$$O(nw)$

Definir nos fornece o modelo de RAM de custo logarítmico tradicional. Porém, alguns algoritmos de RAM inteira são projetados para tamanhos de palavras maiores, como o algoritmo de ordenação inteira em tempo linear de Andersson et al. , Que requer w = Ω ( log 2 + ε n ) .$w = \Theta(\log n)$$w = \Omega(\log^{2+\varepsilon} n)$

Para muitos algoritmos que surgem na prática, o tamanho da palavra simplesmente não é um problema, e podemos (e fazemos) recorrer ao modelo de RAM de custo uniforme muito mais simples. A única dificuldade séria vem de multiplicação aninhada, que pode ser usado para construir muito grandes inteiros muito rapidamente. Se pudéssemos executar aritmética em números inteiros arbitrários em tempo constante, poderíamos resolver qualquer problema no PSPACE em tempo polinomial .$w$

Atualização: devo mencionar também que há exceções ao "modelo padrão", como o algoritmo de multiplicação inteira de Fürer , que usa máquinas de Turing multitape (ou equivalente, a "bit RAM") e a maioria dos algoritmos geométricos, que são analisados ​​teoricamente. modelo "real RAM" limpo, mas idealizado .

Sim, esta é uma lata de vermes.

$n$$O(1)$$O(n)$

Para responder à pergunta como indicado: os algoritmos apenas fazem isso com bastante frequência usando o modelo de RAM. Para classificar, em muitos casos, as pessoas até analisam o modelo de comparação mais simples , que discuto um pouco mais na resposta vinculada.

Para responder à pergunta implícita sobre por que eles fazem isso: eu diria que esse modelo tem um bom poder preditivo para certos tipos de algoritmos combinatórios, nos quais os números são todos "pequenos" e, em máquinas reais, cabem em registradores.

Para responder ao acompanhamento implícito sobre algoritmos numéricos: Não, o modelo antigo de RAM simples não é o padrão aqui. Até a eliminação gaussiana pode exigir algum cuidado. Normalmente, para cálculos de classificação, o Schwartz Lemma entrará (por exemplo, Seção 5 aqui ). Outro exemplo canônico é a análise do algoritmo elipsóide, que requer alguns cuidados para analisar.

E finalmente: as pessoas já pensaram em ordenar as cordas antes , mesmo recentemente.

Atualização: O problema com esta pergunta é que "nós" e "assumimos" não são tão precisamente especificados. Eu diria que as pessoas que trabalham no modelo de RAM não estão usando algoritmos numéricos ou teoria da complexidade (onde determinar a complexidade da divisão foi um resultado célebre ).

$O(1)$$O(1)$

python -mtimeit "$a * $b"$a$10^{\{1,2,...,66\}}$$b = 2*$a

$10^{50}$$\log_{10}(\tt{sys.maxint})$

$O(1)$

$O(\log M)$$O (N \log N)$$O (N \log N \log M)$

$M$

Eu diria que normalmente assumimos operações aritméticas O (1) porque geralmente fazemos coisas no contexto de números inteiros de 32 bits ou de 64 bits ou números de ponto flutuante IEEE 754. O (1) é provavelmente uma boa aproximação para esse tipo de aritmética.

Mas, em geral, isso não é verdade. Em geral, você precisa de um algoritmo para executar adição, subtração, multiplicação e divisão. Boolos, Burgess e Jefferies ' Computability and Logic vêm à mente como uma maneira de entender a (s) prova (s) disso, em termos de dois sistemas formais diferentes, Funções Recursivas e Máquinas de Ábaco, pelo menos na minha cópia da 4ª Edição.

Você pode consultar os termos do cálculo lambda para subtração e divisão com Numerais da Igreja para obter uma explicação fácil de ver por que essas duas operações não são O (1). É um pouco mais difícil ver adição, multiplicação e exponenciação, mas existe se você considerar a forma dos números da igreja.