数据结构（严蔚敏）Chapter 2 Arrays.pptVIP

⑤ Logarithms 二分查找比较次数 r=2s 设s表示步数，r表示有哪些信誉好的足球投注网站范围，r与s的关系归纳如下： s=log2(r) ⑥ Storing Objects 在Java中，数据结构只存储long类型的简单变量，而其他数据类型(int, string等)视为object。 而在现实社会中，存储的数据记录是许多字段的组合 e.g: a personnel record - last name, first name, age, Social Security number, and so forth a stamp collection - the name of the country that issued the stamp, its catalog number, condition, current value, and so on. Person类示例给出对象是如何存储的 THE Person CLASS A constructor enables a new Person object to be created and its fields initialized. The displayPerson() method displays a Person object’s data, and the getLast() method returns the Person’s last name; this is the key field used for searches. THE classDataArray.java PROGRAM Person类的程序是在highArray.java基础上作简单修改： 数组类型改为 Person. 关键字(姓氏)现在是一个String对象，作比较时用 equals() 方法，而非 == 操作符。 if( a[j].getLast().equals(searchName) ) // found item? insert() 方法创建一个新的Person对象 ，插入到数组中，而非long类型。 p40 程序显示了数据存储结构可以通过与简单类型同样的方法来处理对象。 ⑦ Big O Notation Automobiles are divided by size into several categories: Similarly, it’s useful to have a shorthand way to say how efficient a computer algorithm is. In computer science, this rough measure is called Big O notation. subcompacts compacts midsize 目前所见到的算法的大O表示法： 即算法的速度与数据项个数之间的关系 无序数组的插入：常数 新数据总是放在下一个有空的地方，执行一步操作 We can say that the time, T, to insert an item into an unsorted array is a constant K: e.g. hash表的查找 线性查找：与N成正比 在数组数据项的线性查找中，寻找特定数据项所需的比 较次数平均为数据项总数的一半，设数据项总数为N，搜 索时间T与N的一半成正比。 二分查找：与log(N)成正比 Similarly, we can concoct a formula relating T and N for a binary search: Big O notation 与上面的公式表示法类似，但省去了常数k ∵比较算法时，并不在乎具体的微处理器芯片或编译器，需要比较的是对应不同的N值，T如何变化，而不是具体的数字。 ∴不需要常数k。 Big O notation 使用大写字母O，含义为“大约是”. In Big O notation, we would say that： a linear search takes O(N) time； a binary search takes O(log N) time； Insertion into an unordered array takes O(1), or constant time. (常数级时间) excellent good fair O(N2) poor c log2n n n * log2n n^2 n^3 2^n 3^n n! example 1 1） sum=0； （1次） 2） f