Estruturas de dados e algoritmos - Visão geral
Estrutura de dados é uma forma sistemática de organizar os dados para usá-los com eficiência. Os termos a seguir são os termos básicos de uma estrutura de dados.
Interface- Cada estrutura de dados possui uma interface. Interface representa o conjunto de operações que uma estrutura de dados suporta. Uma interface fornece apenas a lista de operações suportadas, tipo de parâmetros que eles podem aceitar e tipo de retorno dessas operações.
Implementation- A implementação fornece a representação interna de uma estrutura de dados. A implementação também fornece a definição dos algoritmos usados nas operações da estrutura de dados.
Características de uma estrutura de dados
Correctness - A implementação da estrutura de dados deve implementar sua interface corretamente.
Time Complexity - O tempo de execução ou o tempo de execução das operações da estrutura de dados deve ser o menor possível.
Space Complexity - O uso de memória de uma operação de estrutura de dados deve ser o mínimo possível.
Necessidade de estrutura de dados
Como os aplicativos estão ficando complexos e ricos em dados, há três problemas comuns que os aplicativos enfrentam hoje em dia.
Data Search- Considere um estoque de 1 milhão (10 6 ) itens de uma loja. Se o aplicativo for para pesquisar um item, ele deve pesquisar um item em 1 milhão (10 6 ) itens toda vez, tornando a pesquisa mais lenta. Conforme os dados aumentam, a pesquisa se torna mais lenta.
Processor speed - A velocidade do processador embora seja muito alta, cai limitada se os dados crescerem para bilhões de registros.
Multiple requests - Como milhares de usuários podem pesquisar dados simultaneamente em um servidor web, até mesmo o servidor rápido falha ao pesquisar os dados.
Para resolver os problemas mencionados acima, as estruturas de dados vêm para resgatar. Os dados podem ser organizados em uma estrutura de dados de forma que nem todos os itens precisem ser pesquisados e os dados necessários possam ser pesquisados quase que instantaneamente.
Casos de tempo de execução
Existem três casos que geralmente são usados para comparar o tempo de execução de várias estruturas de dados de maneira relativa.
Worst Case- Este é o cenário em que uma operação de estrutura de dados específica leva o tempo máximo que pode levar. Se o pior caso de uma operação for ƒ (n), então esta operação não levará mais do que ƒ (n) tempo, onde ƒ (n) representa a função de n.
Average Case- Este é o cenário que descreve o tempo médio de execução de uma operação de uma estrutura de dados. Se uma operação levar ƒ (n) tempo para ser executada, então m operações levarão mƒ (n) tempo.
Best Case- Este é o cenário que descreve o menor tempo de execução possível de uma operação de uma estrutura de dados. Se uma operação levar tempo ƒ (n) para ser executada, a operação real pode levar tempo como o número aleatório que seria máximo como ƒ (n).
Terminologia Básica
Data - Os dados são valores ou conjunto de valores.
Data Item - O item de dados refere-se a uma única unidade de valores.
Group Items - Os itens de dados divididos em subitens são chamados de itens de grupo.
Elementary Items - Os itens de dados que não podem ser divididos são chamados de itens elementares.
Attribute and Entity - Uma entidade é aquela que contém certos atributos ou propriedades, aos quais podem ser atribuídos valores.
Entity Set - Entidades de atributos semelhantes formam um conjunto de entidades.
Field - O campo é uma única unidade elementar de informação que representa um atributo de uma entidade.
Record - Registro é uma coleção de valores de campo de uma determinada entidade.
File - Arquivo é uma coleção de registros das entidades em um determinado conjunto de entidades.