数据结构与算法初阶知识--时间与空间复杂度

@开始数据结构之旅

是什么是数据结构

    通俗来讲，是数据的组织形式。学习数据结构，让我更快，

    更优的写出好的算法，何为好的算法呢，接下来，

    从时间复杂度，和空间复杂度来认识。
1
2
3
4
5

    概括一句话是：
    时间复杂度主要衡量一个算法的运行快慢，
	而空间复杂度主要衡量一个算法运行所需要的额外空间。
1
2
3

数据结构的时间复杂度

  Tips：   算法中的基本操作的  执行次数，为算法 的时间复杂度。
1

数据结构的空间复杂度

  Tips: 是对一个算法在运行过程中 临时 占用 存储空间大小的量度 。
1

估算用O（）

	在时间复杂度里面只看执行次数;
	o(1),代表常数次
	O(N)，代表最大项，执行n次，
	举个例子：
	N^2+2N+10--->2^N
	O(N^2)
	
1
2
3
4
5
6
7

比如：

void Func1(int N)     ** N^2+2N+10--->2^N**
{ 
	int count = 0; 
	for (int i = 0; i < N ; ++ i) 
	{  
	  for (int j = 0; j < N ; ++ j)
	      {  
	            ++count;  
	      } 
	} 
	for (int k = 0; k < 2 * N ; ++ k) 
	 { 
	   ++count;
	 }
 
int M = 10;  
while (M--) 
{
    ++count;
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

void fun(int n) {
  int i=l;
  while(i<=n)
    i=i*2;
}
** 在这里，这不是N，O(N)**
执行次数不到N，每次都2倍的缩短，设执行次数x
N（N个数，原本执行n次）=2^x;
所以   x=loogN
1
2
3
4
5
6
7
8
9

接着来，接着理解递归时间复杂度

  int f ( unsigned int n ) {
    if (n == 0 || n==1) 
      return 1;
    else 
      return n * f(n-1);
  }
  递归n次，结果是n！，不用管！！
  ** 每次执行1次，执行 n 次**
1
2
3
4
5
6
7
8

还有二分法时间复杂度

  
int BinarySearch(int* a, int n, int x)
 {    assert(a);
 
    int begin = 0;    int end = n-1;   
     // [begin, end]：begin和end是左闭右闭区间，因此有=号    
    while (begin <= end)  
      { 
             int mid = begin + ((end-begin)>>1); 
                    if (a[mid] < x) 
                               begin = mid+1; 
                     else if (a[mid] > x) 
                                end = mid-1;       
                     else  
                          return mid;    
     }
 
    return -1; 
 }
** 二分法里面，n/2*（n-1）=x 
	x就是执行次数
**
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

long long* Fibonacci(size_t n) {
    if(n==0)         
    return NULL;        
    long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));    
    fibArray[0] = 0;    
    fibArray[1] = 1;    
    for (int i = 2; i <= n ; ++i)    
    {        
    	fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
    }
 
    return fibArray; }
	**
	malloc创建了新的空间n+1--》O(N)
	**
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

	 int** fun(int n) {
     int ** s = (int **)malloc(n * sizeof(int *));
     while(n--)
     s[n] = (int *)malloc(n * sizeof(int));
     return s;
     **
     	此处开辟的是一个二维数组，数组有n行，
     	每行分别有1,2,3,...n列，所以是n(n + 1)/2个元素空间，
     	空间复杂度为n^2
     **
  }

1
2
3
4
5
6
7
8
9
10
11
12
13