数据结构和算法绪论 学习笔记（二）

之前没怎么用过算法，但最近在看理论的时候，发现其中的一些点其实在我们日常的编码中也是很有体现的......

• 空间复杂度和时间复杂度
• 算法再体验

---

空间复杂度和时间复杂度

效率高一般是指的是算法的执行时间，然而一般具体是怎么衡量的呢？
一般算法效率的度量方法（在计算机程序编写之前，依据统计方法进行统计）：

1、算法采用的策略，方案
2、编译产生的代码质量
3、问题的输入规模
4、机器执行指令的速度

从整体依赖于算法的好坏和问题的输入规模。

简单对比

一个算法是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的，则算法时间取决于两者的综合效果。

为了便于比较同一个问题的不同算法，通常的做法是，从算法中选取一种对于所研究的问题（或算法类型）来说是基本操作的原操作，以该基本操作的重复执行的次数作为算法的时间量度。

---

算法时间复杂度

• 时间频率： 一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。
  一个算法中的语句执行次数称为语句频度或时间频度，记为T(n)。

• 时间复杂度：在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n) 也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用 T(n) 表示，若有某个辅助函数 f(n), 使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作**T(n) = Ｏ(f(n)) , 称 Ｏ(f(n)) ** 为算法的渐进时间复杂度，简称时间复杂度。

在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度 T(n) = O(f(n)) 简称为时间复杂度，其中的 f(n) 一般是算法中频度最大的语句频度。

算法空间复杂度

类似于算法的时间复杂度，空间复杂度作为算法所需存储空间的量度。

一个执行的程序除了需要存储空间来寄存本身随用的指令，常数、变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些为实现所需信息的辅助空间。

若输入数据所占的控件只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的额外空间，否则需要考虑输入本身所需的空间。

• 固定部分： 这块的固定空间的大小与输入/输出的数据的个数多少、数值无关。主要包括指令空间（即代码空间）、数据空间（常量、简单变量）等所占的空间，属于静态空间。
• 可变空间： 这块的可变空间的主要包括动态分配的空间，以及递归栈所需的空间等。这部分的空间大小与算法有关。一个算法所需的存储空间用f(n)表示。S(n)=O(f(n))　　其中n为问题的规模（或大小），S(n)表示空间复杂度。

---

我们可以对比下各种排序，再次理解下时间复杂度和空间复杂度：

出处不记得啦...

以上笔记来源：

时间复杂度和空间复杂度1
时间复杂度和空间复杂度2
【数据结构】——严蔚敏 版本
参考：算法的时间复杂度和空间复杂度-总结, 这里写的很赞。

---

算法再体验：

单纯的一个数组列表（@[@"",@""]） 转化成 数组套字典，字典中再套数组的的数组(@[@{@"":@[@"",@""]},@{@"":@[@"",@""]}])

@[
    @{
        @"name" : @"t11",
        @"id"   : @"10001",
        @"class": @"A"
    },
    @{
        @"name" : @"t22",
        @"id"   : @"10002",
        @"class": @"B"
    },
    @{
        @"name" : @"t33",
        @"id"   : @"10003",
        @"class": @"C"
    },
    @{
        @"name" : @"t44",
        @"id"   : @"10004",
        @"class": @"A"
    },
    @{
        @"name" : @"t55",
        @"id"   : @"10005",
        @"class": @"B"
    },
    @{
        @"name" : @"t66",
        @"id"   : @"10006",
        @"class": @"C"
    }

 ]

转化为

@[
    @{
        @"newModels" :  @[
                            @{
                                @"name" : @"t11",
                                @"id"   : @"10001"
                            },
                            @{
                                @"name" : @"t44",
                                @"id"   : @"10004"
                            }
                        ],
        @"class"    : @"A"
    }
    @{
        @"newModels" :  @[
                            @{
                                @"name" : @"t22",
                                @"id"   : @"10002"
                            },
                            @{
                                @"name" : @"t55",
                                @"id"   : @"10005"
                            }
                        ],
        @"class"    : @"B"
    }
    @{
        @"newModels" :  @[
                            @{
                                @"name" : @"t33",
                                @"id"   : @"10003"
                            },
                            @{
                                @"name" : @"t66",
                                @"id"   : @"10006"
                            }
                        ],
        @"class"    : @"C"
    }

 ]