动态查找表

Share

由静态查找表观察，可得一下结论

  • 从查找性能看，最好情况能达O(logn)，此时要求表有序
  • 从插入和删除的性能来看，最好情况能达O(1)，此时要求存储结构为链表

本篇文章是对各种查找树的一个简单概括，具体分析会慢慢更新

More →

静态查找表

Share

静态查找表：仅做查询和检索操作的查找表

假设静态查找结构为

1
2
3
4
5
6
typedef struct {
	elemType *elem;
	//数据元素存储空间基址，建表时按数据长度分配，0号单元留空
	int length;
	//表的长度
}SSTable;

More →

二叉查找树

Share

查找树(search tree)是一种数据结构，它支持多种动态集合操作，包括 SEARCH , MINIMUN , MAXIMUN , PREDECESSOR , SUCCESSOR , INSERT 以及 DELETE。它既可以用作字典，也可以用作优先队列。

在二叉查找树(binary search tree)上执行的基本操作的时间与树的高度成正比。对于一颗含有n个结点的完全二叉树，这些操作的最坏运行时间为O(lgn)。但是，如果树是含有n个结点的线性链，则这些操作的最坏情况为O(n)。在下文可以看到，一颗随机构造的二叉查找树的期望高度为O(lgn)，从而这种树上基本动态集合的平均操作时间为O(lgn)

More →

详探贪心算法

Share

贪心算法的基本内容

贪心算法是通过做一系列的选择来给出某一问题的最优解。对算法中的每一个决策点，做一个当时看起来是最佳的选择。这种启发式策略并不是总能产生最优解，但正如我们在哈夫曼问题中看到的那样，它常常能给出最优解。此篇文章我们来讨论讨论贪心算法的某些一般性质。

More →

代码签名探析

Share 
"用户会感激代码签名带来的好处" – Apple Developer Library

在 iOS 或 macOS 平台上进行应用开发时，你所需要使用的 API 大多设计得简洁明了。你可以轻易地实现酷炫的动画效果，便捷地进行应用发布前测试，或是用 Core Data 将数据安全的存储在本地。但是总有一天，你会碰上代码签名 (code signing) 和配置文件 (provisioning)，大多数情况下，这会是你在心里问候某些人祖宗的开始。

More →

浅谈iOS的模糊效果

Share

iOS的模糊效果实现方法有好几种，基本分为两种方式，一种是将图片进行模糊，一种是将模糊的控件放在UI界面上，使控件覆盖的区域达到模糊的效果。每种方式我各选了2种方法，下面介绍一下它们的实现方式以及对比一下它们的优缺点。

coreImage

More →

Huffman树以及Huffman编码

Share

Huffman树是一种存储结构，由于国内有的资料翻译为哈夫曼或者是霍夫曼，这里为了简单（当然不是懒了）就是用英语Huffman代替。

解决Huffman树问题是典型的贪心算法问题。

贪心算法

贪心算法又叫贪婪算法，是指在对问题求解释，总是做出当前看来是最好的选择。

当一个问题具有以下性质时可以用贪心算法求解：每一步的局部最优解，同时也是整个问题的最优解。

More →