一.简介
- 向量是数组的抽象和泛化
- 向量使用地址连续的物理空间
- 在向量的末尾添加一个哨兵,可以更方便观察和测试向量
二.向量的扩充
- 采用静态空间管理策略,所以向量本质上是不可扩充的
- 向量存在的问题:
向量上溢:_elem[ ] 不足以存放所有元素
向量下溢:_elme[ ] 没有什么元素,浪费空间(_size/_capacity << 50%)
-
向量扩容方法1:在向量达到容量最大值的时候,重新开辟一个容量原向x2,并把原向量的内容copy到现向量.(节省时间,牺牲了空间)
-
向量扩容方法2:在向量达到容量最大值的时候,增加_elem相应的capacity.(空间利用率达100%,但是扩容这个操作非常浪费时间)
-
分摊复杂度比平局复杂度可以更准确的反应算法的优劣
三.无序向量
四.有序向量
1.有序向量的唯一化
- 相邻逆序对的数量,可以度量向量的逆序程度.
1.低效版
一一比对和判断,删除重复的元素.
删除第一位,后续的也都需要往前移动,所以时间复杂度为O(n * 2)
和无序向量的去重效率一样
2.高效版
赋值不重复元素到前面,然后设置向量的长度.
不使用remove操作,却变相删除了重复元素.
NSDate *date = [NSDate date];
NSArray *arr = @[@3,@3,@3,@5,@5,@8,@8,@8,@13];
NSMutableArray *muArr = [NSMutableArray arrayWithArray:arr];
NSInteger leading = 0;
for (int i = 0; i < muArr.count - 1; i ++)
{
if([muArr[leading] integerValue] < [muArr[i + 1] integerValue])
{
muArr[leading + 1] = muArr[i + 1];
leading ++ ;
}
}
NSLog(@"%@",[muArr subarrayWithRange:NSMakeRange(0, leading + 1)]);
NSLog(@"%lf",[[NSDate date] timeIntervalSinceDate:date]);
//结果: 3, 5, 8, 13
//耗时: 0.000211
2.有序向量的二分查找
二分查找的时间复杂度为1.5 * O(log 2 的n次方)
3.有序向量的Fibonacci查找
fibnacci查找的时间复杂度为1.44*O(log 2 的n次方)
mid为黄金分割数
4.有序向量的二分查找(优化)
theWanted < mid
theWanted > mid
theWanted == mid
优化后的二分查找将 theWanted > mid & theWanted == mid合并,减少右侧查找的计算量
总结:新算法更稳定(原来的算法好的情况特别好,坏的情况右侧计算量巨大)
5.有序向量的插值查找
- 插值查找的时间复杂度为O(loglgo n)
插值查找,类似字典的用法.如果想找z开头的汉字,你就直接翻到最后的几页
如果元素是均匀独立分布的,那么用插值查找效率会很高.
如果元素是相当随机散乱的,那么用插值查找效率和依次查找的效率一样低.
五.气泡排序
- 冒泡排序最好的情况下O(n),最坏的情况下O(n的2次方),这和算法无关
//冒泡1
NSArray *theArr = @[@98,@9,@13,@43,@100,@105,@109];
NSMutableArray *arr = [NSMutableArray arrayWithArray:theArr];
NSDate *date1 = [NSDate date];
for (int i = 0; i < arr.count; i ++)
{
for (int j = i + 1; j < arr.count;j++)
{
if([arr[i] integerValue] > [arr[j] integerValue])
{
NSNumber *temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
NSLog(@"%@",arr);
NSLog(@"%lf",[[NSDate date] timeIntervalSinceDate:date1]);//0.000237
//冒泡2
NSMutableArray *muArr = [NSMutableArray arrayWithArray:theArr];
NSDate *date2 = [NSDate date];
for (int i = 0; i < muArr.count; i ++)
{
for (int j = 0; j <muArr.count - i - 1 ; j ++)
{
if([muArr[j] integerValue] > [muArr[j + 1] integerValue])
{
NSNumber *temp = muArr[j];
muArr[j] = muArr[j + 1];
muArr[j + 1] = temp;
}
}
}
NSLog(@"%@",muArr);
NSLog(@"%lf",[[NSDate date] timeIntervalSinceDate:date2]);//0.000153
- 第一种算法,0位依次和其他比较,然后1位依次和其他比较.
- 第二种算法,0位和1位比较,1位和2位比较.
- 第二种的计算时间短,因为像demo中的数组,后面几个元素是有序的,所以不必再进行交换.而第一种算法每次都要和0位、1位交换,所以话费时间较多.
但这和数组的元素有关,只能说demo中的数组更适合用第二种方法
冒泡排序优化:增加一个变量记录上一次扫描过程中最后一个乱序对,如果没有乱序对,就说明已经全部有序,那么就不用进行不必要的for循环了,直接提前退出.如果有乱序对在接下来的扫描中就把high的秩降到记录的乱序对的秩.
//冒泡优化,有点不一样了,慢慢适应吧
NSMutableArray *muArr = [NSMutableArray arrayWithArray:theArr];
NSDate *date2 = [NSDate date];
NSInteger last = muArr.count;
while (last != 1)//当last==1时,说明全部排序完了.
{
NSInteger haveDiff = 1;
for (int j = 0; j < last - 1; j ++)
{
if([muArr[j] integerValue] > [muArr[j + 1] integerValue])
{
NSNumber *temp = muArr[j];
muArr[j] = muArr[j + 1];
muArr[j + 1] = temp;
haveDiff = j + 1;
}
}
last = haveDiff;//上一次全部循环完后,记录最后一个逆序对的秩.
}
NSLog(@"%@",muArr);
NSLog(@"%lf",[[NSDate date] timeIntervalSinceDate:date2]);
六.归并排序
待看.
七:总结
- 最合适的才是最好的.
-
根据情况多种算法相结合
图片.png
网友评论