演演算法的空間複雜度

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 /**
 6  * 功能： 查詢陣列下標並返回
 7  * 引數：
 8  *  a[]： 輸入資料
 9  *  n：陣列長度 
10  *  v：待查詢的元素
11  * 返回值：待查詢元素的陣列下標
12 */
13 int find(int a[], int n, int v)
14 {
15     int ret = -1;
16 
17     for(int i = 0; i < n; i++)  // O(n)
18     {
19         if( a[i] == v)
20         {
21             ret = i;
22             break;
23         }
24     }
25 
26     return ret;
27 }
28 
29 
30 
31 int main(int argc, char* argv[])
32 {
33     int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
34     int length = sizeof(arr)/sizeof(int);
35     int min = find(arr, length, 1);     // 最好情況，演演算法執行1次，O(1)
36     int max = find(arr, length, 10);    // 最差情況，演演算法執行10次，O(10)
37 
38     return 0;
39 }

 1 // sum1() 空間複雜度 = n+4
 2 long sum1(int n)    // 1
 3 {
 4     long ret = 0;   // 1
 5     int* array = new int[n];    // n
 6     
 7     for(int i=0; i<n; i++)  // 1
 8     {
 9         array[i] = i + 1;
10     }
11     
12     for(int i=0; i<n; i++)  // 1
13     {
14         ret += array[i];
15     }
16     
17     delete[] array;
18     
19     return ret;
20 }

 1 /*
 2     問題： 
 3     在一個由自然數1-1000中某些數位所組成的陣列中，每個數位可能出現零次或者多次。
 4     設計一個演演算法，找出出現次數最多的數位。
 5 */
 6 
 7 #include <iostream>
 8 
 9 using namespace std;
10 
11 int search(int a[], int len)
12 {
13     int sp[1000] = {0}; // 初始化每個自然數出現的次數，陣列下標加1代表當前的自然數
14     int max = 0;    // 儲存自然數出現次數的最大值
15     int ret = 0;    // 儲存出現次數最多的自然數
16     
17     for(int i=0; i<len; i++)
18     {
19         sp[a[i] - 1]++; // 標記自然數的出現次數
20     }
21     
22     for(int i=0; i<1000; i++)
23     {
24         if( max < sp[i] )
25         {
26             max = sp[i];
27         }
28     }
29     
30     for(int i=0; i<1000; i++)
31     {
32         if( max == sp[i] )
33         {
34             ret = i + 1;
35             break;
36         }
37     }
38 
39     return ret;
40 }
41 
42 int main(int argc, char* argv[])
43 {
44     int a[] = {1, 1, 3, 4, 5, 6, 6, 6, 3, 3, 6};
45     
46     int ret = search(a, sizeof(a)/sizeof(*a));
47     
48     cout << ret << endl;
49 
50     return 0;
51 }