数据结构错题记录（1）

1.

线性表长度的定义是它所包含的元素的个数
元素的类型决定了元素所占用存储空间的大小，但元素的个数不等价于元素的类型

2.

O(1)
    常数复杂度, 最快的算法
    取数组第1000000个元素
    字典和***的存取都是O(1)
    数组的存取是O(1)

O(logN)
    对数复杂度
    假设有一个有序数组, 以二分法查找

O(n)
    线性复杂度
    假设有一个数组, 以遍历的方式在其中查找元素

O(nlogn)
    求两个数组的交集, 其中一个是有序数组
    A数组每一个元素都要在B数组中进行查找操作
    每次查找如果使用二分法则复杂度是 logN

O(n2)
    平方复杂度
    求两个无序数组的交集