C++STL之哈希表
C++ STL中,哈希表对应的容器是unordered_map(since C++ 11)。
STL中,map 对应的数据结构是 红黑树。红黑树是一种近似于平衡的二叉查找树,里面的数据是有序的。在红黑树上做查找操作的时间复杂度为 O(logN)。而 unordered_map 对应 哈希表,哈希表的特点就是查找效率高,时间复杂度为常数级别 O(1), 而额外空间复杂度则要高出许多。所以对于需要高效率查询的情况,使用 unordered_map 容器。而如果对内存大小比较敏感或者数据存储要求有序的话,则可以用 map 容器。
说明
unordered_map 是一种关联容器,用于存储由关键值 (Key Value,以下称为Key 值) 和映射值 (Mapped Value,以下称为映射值) 组成的元素,并且允许根据其 Key 值快速检索各个元素。
在 unordered_map 容器中,Key 值通常用来唯一标识元素,映射值是与该 Key 值关联内容的对象。Key 值与映射值的类型可能不同。
在 unordered_map 内部,元素没有按照其 Key 值与映射值的任何顺序进行排序 ...
博客搭建记录
2023.2发布文章生成markdown文件,在命令行输入:
hexo n "文章标题"
在blog根目录下的source文件夹中的post文件夹会多一个 博客名字.md 的markdown文件,打开即可进行编辑。
写文章markdown语法参考链接 Markdown语法说明(简体中文版)
Hexo部署在根目录下git命令行输入三连指令,即可完成新页面的发布
hexo clean && hexo g && hexo d
如果在发布前想预览生成网站的效果,可输入
hexo s
2024.7.25近日心血来潮地想起自己两年前心血来潮搭的网站,想到自己已经为这个域名掏了三年的钱包,还是要好好利用起来,于是再次开始维护。
主页顶部图片更改维护时首先想到的就是把主页顶部图片换了,顶部图片的更换非常简单,我目前使用的是butterfly主题,只需要在_config.butterfly.yml中修改index_img后的图片链接即可:
# The banner image of home page (主页封面图片)index_img: /img/ ...
NP问题
NP问题
NP问题 的全称是:Non deterministic Ploynomial问题,即非确定性多项式问题。
多项式时间(Polynomial time) 在计算复杂度理论中,指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。
什么是非确定性问题?
有些计算问题是确定性的,比如加减乘除之类,你只要按照公式推导,按部就班一步步来,就可以得到结果。但是,有些问题是无法按部就班直接地计算出来。比如,找大质数的问题。有没有一个公式,你一套公式,就可以一步步推算出来,下一个质数应该是多少呢?这样的公式是没有的。再比如,大的合数分解质因数的问题,有没有一个公式,把合数代进去,就直接可以算出,它的因子各自是多少?也没有这样的公式。
这种问题的答案,是无法直接计算得到的,只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法,它不能直接告诉你答案是什么,但可以告诉你,某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法,假如可以在多项式时间内算出来,就叫做多项式非确定性问题。
NP问题 就是非确定性的多项式问题,也就是 ...