向量

2018-05-07 本文已影响0人李永开

一.简介

向量是数组的抽象和泛化
向量使用地址连续的物理空间
在向量的末尾添加一个哨兵,可以更方便观察和测试向量

二.向量的扩充

采用静态空间管理策略,所以向量本质上是不可扩充的
向量存在的问题:

向量上溢:_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

向量