数据结构(1)—— 几个基础概念及问题

    技术2022-07-11  127

    关于空间的使用: 解决问题方法的效率,跟空间的利用效率有关

    典型案例: 使用for循环和递归顺序打印10000000,递归会非正常结束

    关于算法效率:

    时间测试:

    #include <iostream> #include <ctime> using namespace std; /*clock_t是clock()函数返回的变量类型*/ clock_t start,stop; /*记录被测函数运行时间,以秒为单位*/ double duration; int main() { start = clock(); // 开始计时 /* 待测代码 */ stop = clock(); //停止计时 duration = ((double)(stop-start))/CLK_TCK; cout << duration <<endl; return 0; }

    如果程序跑太快,导致无法比较时间,解决方案如下:

    重复运行被测函数多次,使得测出的总时钟打点间隔充分长,最终计算被测函数平均每次运行时间即可。

    什么是数据结构: 数据对象在计算机中的组织方式:

    逻辑结构物理存储结构

    数据对象必定与一系列加在其上的操作相关联,完成这些操作所用的方法即算法

    抽象数据类型(Abstract Data Type):

    数据类型 数据对象集数据集合相关联的操作集 描述数据类型的方法不依赖于具体实现 与存放数据的机器无关与数据存储的物理结构无关与实现操作的算法和编程语言均无关

    只描述数据对象集和相关操作集“是什么”,并不涉及“如何做到”

    什么是算法:

    什么是好的算法? 复杂度的渐进表示法:

    复杂度分析小窍门: 实例:最大子列和问题

    在看到算法复杂度为O(N^2)时,应该首先想到能不能提高到O(NlogN)!!!

    “在线”的意思是指每输入一个数据就进行即时处理,在任何一个地方终止输入,算法都能正确给出当前的解。

    以上四种算法的对比效果:


    浙江大学陈越、何钦铭老师的《数据结构》学习笔记
    Processed: 0.010, SQL: 9