数据结构与算法

平时开发中,一般很少用到手动来写算法的情况,但实际上我们一直在接触一些数据结构与算法,如JAVA中的ArrayList 就用到了数据结构与算法,从名字可以看到了用到了Array这种数组结构和链表结构。下面根据目前学习的情况做一个总结。

数据结构

我们常见的数组结构一般有:

  • Array数组、
  • Stack栈、
  • Heap堆、
  • Queue队列
  • Hash 哈希类型
  • LinkedList 链表,其中又分为单向链表、双向链表、还有最少用的环形链表
  • Tree 这个Tree分的太多了,如B-Tree、 B+Tree(mysql使用)、Binary Search Tree二叉搜索树 、AVL高度平衡树、Red Black Tree红黑树 等
数据结构

http://www.bigocheatsheet.com/

 

算法

一般开发中用到的基本上排序算法居多,而算法大体上又分为比较排序和非比较排序。我们常用的比较排序算法有(参考:http://www.cnblogs.com/eniac12/p/5329396.html):

  • 快速排序 (Quick Sort)
  • 冒泡排序 (Bubble Sort)
  • 插入排序 (Insertion Sort)
  • 堆排序 (Heap Sort)
  • 归并排序 (Merge Sort)

而非比较排序算法有(由于排序算法时间复杂度是线性的,有时候我们也称此算法线性排序,参考http://www.cnblogs.com/eniac12/p/5332117.html):

  • 计数排序(Counting sort)
  • 基数排序 (Radix Sort)
  • 桶排序 (Bucket Sort)

http://www.bigocheatsheet.com/

 

Bucket sort 排序

Bucket sort 排序 (图出自:极客时间)

计数排序 Counting sort

计数排序 Counting sort (图出自:极客时间)

注意:
有些算法是属于稳定算法,也有些属于非稳定算法。所谓的稳定是指相同的排序值原来的顺序经过排序后,前后顺序并不改变。就像我们平时数据库中根据两个字段进行排序的时候一样。

算法时间复杂度和空间复杂度
时间复杂度:https://baike.baidu.com/item/时间复杂度/1894057
空间复杂度:https://baike.baidu.com/item/空间复杂度

复杂度大致可分为:

  • O(1) 最好
  • O(log n)
  • O(n)
  • O(n log n)
  • O(n^2)
  • O(2^n)
  • O(n!) 最差

O(log n):当数据增大n倍时,耗时增大log n倍(这里的log是以2为底的,比如,当数据增大256倍时,耗时只增大8倍,是比线性还要低的时间复杂度)。二分查找就是O(logn)的算法,每找一次排除一半的可能,256个数据中查找只要找8次就可以找到目标。

O(n log n):同理,就是n乘以logn,当数据增大256倍时,耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。

O(n^2),就代表数据量增大n倍时,耗时增大n的平方倍,这是比线性更高的时间复杂度。比如冒泡排序、插入排序、选择排序,就是典型的O(n^2)的算法,对n个数排序,需要扫描n x n次。

Heap And Stack 堆与栈的区别

堆与栈的区别

推荐:https://www.programmerinterview.com/index.php/data-structures/difference-between-stack-and-heap/

栈是上下顺序存储的,且“先进后出LIFO”规则,只能删除顶部的元素,而堆是没有特定的顺序的存储,您可以删除任意元素。堆分配需要维护分配的内存和未分配的内存的完整记录,以及一些开销维护以减少碎片,找到足够大以适应请求大小的连续内存段,等等。内存可以随时释放,留出自由空间。有时,内存分配器将执行维护任务,比如通过将分配的内存到处移动来对内存进行碎片整理,或者在运行时进行垃圾收集——当内存不再处于作用域中时对其进行标识并释放它。

1. 栈用在线程中,程序执行时由线程创建有限数量的栈空间,当线程结束的时候会自动回收,属于系统级。
堆一般是由应用程序在启动时创建,由应用程序回收,属于应用级。

The stack is attached to a thread, so when the thread exits the stack is reclaimed. The heap is typically allocated at application startup by the runtime, and is reclaimed when the application (technically process) exits.

2. 栈的大小固定,通常在程序启动时已经确定了最大大小(部分语言支持动态扩容)。如果超出会出现“stack overflow”异常,经常在“递归”函数里出现。
堆是由”动态分配“的,其大小不固定,你可以在任何时间创建,再在任何时间回收(还是受限限系统虚拟内存 (ie: RAM and swap space))。

3. 每个线程可有一个堆栈,而应用程序通常只有一个堆(尽管对于不同类型的分配有多个堆并不罕见)

4. 栈的读取速度要更快。因为分配内存的机制,只是移动指针,而堆还要做查找等操作。

Which is faster – the stack or the heap? And why?

The stack is much faster than the heap. This is because of the way that memory is allocated on the stack. Allocating memory on the stack is as simple as moving the stack pointer up.

 

Variables allocated on the stack, or automatic variables, are stored directly to this memory. Access to this memory is very fast, and it’s allocation is dealt with when the program is compiled. Large chunks of memory, such as very large arrays, should not be allocated on the stack to avoid overfilling the stack memory (known as stack overflow). Stack variables only exist in the block of code in which they were declared. For example:

堆和栈在内存分配方面的不同:http://timmurphy.org/2010/08/11/the-difference-between-stack-and-heap-memory-allocation/

5. 堆和栈在用在函数变量的时候有些不同,一般动态创建的变量是存储在堆heap中,访问速度慢一些,而放在栈里的变量访问速度要快的多。

Variables allocated on the heap, or dynamic variables, have their memory allocated at run time (ie: as the program is executing). Accessing this memory is a bit slower, but the heap size is only limited by the size of virtual memory (ie: RAM and swap space). This memory remains allocated until explicitly freed by the program and, as a result, may be accessed outside of the block in which it was allocated.

如编码中的定义一个变量 int i = 20 则变量 i 存储在stack中;创建一个对象 user = new Account(); //这时user变量则存储在heap中。

堆与栈用法示例

int foo()
{
  char *pBuffer; //<--nothing allocated yet (excluding the pointer itself, which is allocated here on the stack).
  bool b = true; // Allocated on the stack.
  if(b)
  {
    //Create 500 bytes on the stack
    char buffer[500];

    //Create 500 bytes on the heap
    pBuffer = new char[500];

   }//<-- buffer is deallocated here, pBuffer is not
}//<--- oops there's a memory leak, I should have called delete[] pBuffer;

https://stackoverflow.com/questions/79923/what-and-where-are-the-stack-and-heap

http://www.programmerinterview.com/index.php/data-structures/difference-between-stack-and-heap/

视频 https://www.youtube.com/watch?v=450maTzSIvA

https://blog.csdn.net/waidazhengzhao/article/details/76651923