Desculpas pela pergunta do novato, mas estou um pouco confuso sobre o que exatamente conta como uma "operação simples" ao calcular a complexidade de tempo de um algoritmo. Em particular, por que consideramos todas as operações iguais?
Certamente, dividir dois números muito grandes consome mais tempo do que adicionar um a um número (como em cada iteração de um loop for). A multiplicação, por exemplo, pode consistir em qualquer número de pequenas adições. Então, em vez de apenas adicioná-los, não deveríamos aplicar algum tipo de peso a cada operação, dependendo do tipo de operação (adição, multiplicação, etc.) e do tamanho dos números envolvidos?
Meu problema é que me pedem para provar que a complexidade do meu algoritmo é (para alguma função ) e não tenho certeza de como fazer isso de maneira matematicamente rigorosa devido à imprecisão inerente na definição de "operação simples". Então, como eu iria fazer isso?
fonte
Respostas:
Operações simples são algo que leva tempo constante para ser alcançado. A confusão é que a divisão não parece levar tempo constante e, de fato, em geral, não é. MAS!
A divisão e a adição levam tempo constante se, por exemplo, você estiver adicionando dois números inteiros de 32 bits, o que geralmente ocorre. No entanto, se você estiver adicionando números arbitrariamente grandes, eles não serão realmente constantes, embora às vezes eu ache que as pessoas o tratem como se fosse porque é suposto que os números não são grandes demais.
fonte