数据结构之基本概况

Posted on | In |

基本概况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <math.h>
#include <time.h>

#define MAXN 10
#define MAXK 1e7

//多项式给定处的值
//f(x)=a0+a1x+a2x^2+....+anx^n
double f1(int n, double a[], double x)
{
    double sum = a[0];
    for (int i = 1; i <= n; i++) {
        sum += (a[i] * pow(x,i));
    }
    return sum;
}

////f(x)=a0+x(a1+x(...(an-1+x(an))...))
double f2(int n, double a[], double x)
{
    double sum = a[n];
    for (int i = 1; i <= n; i++) {
        sum += a[n - 1] + x * sum;
    }
    return sum;
}

//函数作为参数
void run(double(*f)(int n, double *, double), double a[], int func_n) {
    clock_t start = clock();
    for (int i = 0; i < MAXK; i++) {
        f(MAXN - 1, a, 1.1);
    }
    clock_t stop = clock();
    double duration = ((double)(stop - start)) / CLOCKS_PER_SEC / MAXK;
    printf("ticks%d = %f\n",func_n,(double)(stop - start));
    printf("duration%d = %6.2e\n",func_n,duration);
}

void test()
{
    
    double a[MAXN];
    a[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        a[i] = (double)i;
    }
    
    run(f1, a, 1);
    run(f2, a, 2);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/*
 时间复杂度最好:O(1)
 时间复杂度最坏:O(logN)
 空间复杂度:O(1)
 */
int binarySearch(int arr[], int n, int key) {
    int low = 0;
    int high = n - 1;
    int ret = -1;
    int mid;
    while (low < high) {
        mid = (low + high) / 2;
        if (arr[mid] > key) {
            high = mid - 1;
        }
        else if (arr[mid] < key) {
            low = mid + 1;
        }
        else {
            ret = mid;
            break;
        }
    }
    
    return  ret;
}