Análise de algoritmos

Veja a página Analysis of Algorithms (S&W).

O livro faz bastante propaganda do método científico. Algo que vocês devem estar vendo em MAC0209 ou em disciplinas de ciências.

O livro a notação ~f(m) para descrever o consumo de tempo ou memória usada pelos programas. Isso significa que o tempo ou espaço usado pelo programa é proporcionais a f(m).

É legal a preocupação com o espaço, que normalmente é deixado de lado. Essa página descreve como estimar o espaço usado pelo programa. Cada referência gasta 8 bytes. Overhead de um objeto gasta 16 bytes de overhead. Se objeto é de uma subclasse gasta mais uns 8 bytes de overhead. O exemplo típico de subclasse é Node que usamos para listas ligadas e árvores. boolean e byte gastam 1 byte. char gasta 2 pois a codificação é UTF-8. int e float gastam 4 bytes e long e double gastam 8. Só tem número redondo 1, 2, 4, 8, 16.

Leia as Questões e Respostas (Q + A) dessa página (e das outras). Vocês podem achar coisas bem interessantes.

Tem vários exercícios bem legais. Eles estão, talvez, mais relacionados com MAC0338, normal. Ferramentas básicas são busca binária e ordenação, acho.

• Exercises: 6 está resolvido e é bem fundamental
• Creative problems: 24 e 25 são divertidos.
• Web exercises: 4, 8, 9, 25 são todos legais. 26, 27 e 28 mostram programas para estimar o uso de memória.