ADT and Time Complexity

1

• • • • • • • •

Data and Data Type Abstract Data Type(ADT) Application Level Logical Level Implementation Level Data Structure Data Abstraction Information Hiding
2

Data and Data Type
• Data: something that stores information and have operations. • Data Type: a group of data that share same characteristics Example: int is a data type. int i,j. i and j are data, they have operations ++,+,-,x, %. int i,j; i++; i--;
3

Object Description
• Consider not a single object but a type of objects with similar properties. • Define each type of objects not by the objects’ physical representation but by their behavior: the services (FEATURES) they offer to the rest of the world. • External, not internal view: ABSTRACT DATA TYPES
4

• There are two companies, each has three employees. We need store information about salary of employees and we want to operations such as increase salary, decrease salary, observe salary.

5

ADT
Salary companyA, companyB; companyA.increaseSalary(0.3)// increase salary by 30% companyB.decreaseSalary(0.4)// decrease salary by 40% companyA.ObserveSalary() Salary stores information and have operations, so Salary is a data type. The operations are specified independently of implementation, so Salary is a Abstract Data Type(ADT). ADT: A data type whose domain and operations are specified independently of any particular implementation.

6

Logical Level
An abstract view of the data values and the set of operations to manipulate them. In logical level, we design the data. class Salary{ public: initialize(); increaseSalary (float percent); ObserveSalary(); decreaseSalary(float percent); private: // salaries for three employees. }
7

Application Level
Application Level: the way of modeling real-life data in a specific context, that is how we use the data type in applications. In application level, we use the data. Example: companyA.increaseSalary(0.3); companyB.ObserveSalary();

8

Implementation Level
A specific representation of the structure to hold the data items, and the coding of the operations in a programming language

9

One Implementation class Salary{ public: initialize(); increaseSalary (float percent); ObserveSalary(); decreaseSalary(float percent); private: float employee1,employee2,employee3; } Salary::increaseSalary(float percent){ employees1 = employees1*(1+percent); employees2 = employees2*(1+percent); employees3 = employees3*(1+percent); } …….

10

Another Implementation class Salary{ public: initialize(); increaseSalary (float percent); ObserveSalary(); decreaseSalary(float percent); private: float employees[3]; } Salary::increaseSalary(float percent){ for(int i=0;i