欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【ZJU数据结构笔记】复习前准备

程序员文章站 2022-03-27 10:33:32
...

2020.02.22到了周末,大致的计划是看看自己周一到周五的题目的题解,然后再次进行练习,同时在bilibili上重修一下ZJU陈越姥姥的数据结构课,补一下已经忘掉的知识点


对程序和算法使用clock()捕捉调用耗费时间

clock():捕捉从程序开始运行到clock()被调用时所耗费的时间,单位时clock tick"时间打点"
常数CLK_TCk:机器时钟每秒所走的时钟打点数

#include<stdio.h>
#include<time.h>
//clock_t是clock()函数返回的变量类型
clock_t start ,stop;
//以秒为单位计算函数运行时间
double duration;
int main(){
  start = clock();
  Function();//此处插入函数
  stop = clock();
  duration = ((double)(stop - start) / CLK_TCK);
  return 0;
}

若函数的运行时间还不够一个tick,想要比较两个函数的调用时间,只需要让被测函数重复运行充分多次,使得测出的总时钟打点间隔充分长,最后计算被测函数平均每次运行的时间即可


什么是算法?

有限的指令集 + 接受输入(有些情况不需要输入) + 产生输出 + 在一定有限步骤后终止
一个好的算法的衡量角度

空间复杂度S(N) : 算法写成的程序在执行时占用存储单元的长度
时间复杂度T(N) :算法写成的程序在执行时耗费时间的长度
//N与问题规模有关

好的算法
经常关注以下两种复杂度
T-worst(n)最坏情况复杂度(更常分析)
T-avg(n)平均复杂度
使用复杂度的渐进表示法,上界(O(n))和下界(Ω(n))不唯一,但要注重分析效率,尽量贴合真实情况
【ZJU数据结构笔记】复习前准备【ZJU数据结构笔记】复习前准备避免N3到N的阶乘的算法!!!有意识的去优化N2算法,降低复杂度

复杂度分析小窍门

【ZJU数据结构笔记】复习前准备