codenote

时间复杂度

探讨一个算法的实现以及其性能，表示程序运行答题时间。
f(n)指的是一般数据下运行时间的上界，并非一定是最坏情况，所以要注意：

• 数据用例不同时时间复杂度不同。
• 时间复杂度不同时，不同输入数据规模下性能也会有差异（就是函数问题）；O是数据量级非常大的情况下表现出的时间复杂度，所以经常会忽略常数项，所以说决定算法并不是只考虑复杂度越低越好还要综合数据规模
• 化简：只保留最高次（考虑n很大况）
• 注意考虑全面’每次操作’的内涵 eg.字符串比较，有字符串自身长度m，排序后比较比直接比较更优
• 递归的时间复杂度：递归次数*递归中的操作次数；[tips]在递归中要少调用自身函数，建议单独把要调用的函数抽取出来，可以减少时间复杂度(下例时间复杂度n/2)

  int function4(int x, int n) {
      if (n == 0) return 1;
      if (n == 1) return x;
      int t = function4(x, n / 2);// 这里相对于function3，是把这个递归操作抽取出来
      if (n % 2 == 1) {
          return t * t * x;
      }
      return t * t;
  }

  补充：空间复杂度
  空间复杂度是程序运行时占用内存的大小，不是exe文件本身大小

排序

二分法

快速排序

内置函数：sort(pbegin,pend);

qsort函数compare

qsort(a,n,bytes(type),compare);

• 是相应的数据类型单个变量所占的字节数

Sort double array

int n;
double a[N];
int compare(const void *e1, const void *e2)
{
    double v1 = *((double *)e1);
    double v2 = *((double *)e2);
	if(v1 > v2) return 1;
	if(v1 < v2) return -1;
	return 0;
}
qsort(a, n, sizeof(double), compare);

Sort long long array

int n;
long long a[N];

int compare(const void *e1, const void *e2)
{
    long long v1 = *((const long long *)e1);
    long long v2 = *((const long long *)e2);
	if(v1 > v2) return 1;
	if(v1 < v2) return -1;
	return 0;
}

qsort(a, n, sizeof(long long), compare);

Sort array of char array

char buf[100][105];
int n;

qsort(buf, n, sizeof(buf[0]), strcmp);

// Sort char* array
char *lines[100];
int n;

int compare(const void *p1, const void *p2)
{
    char *a = *(char **)p1;
    char *b = *(char **)p2;
    return strcmp(a, b);
}

qsort(lines, n, sizeof(char *), compare);

Sort array of int array

int data[100][3];
int n;

int compare(const void *e1, const void *e2)
{
    int *p1 = (int *)e1;
    int *p2 = (int *)e2;
	if(p1[0] > p2[0]) return 1;
	if(p1[0] < p2[0]) return -1;
	// You can use p[1], p[2] as well
	return 0;
}
qsort(buf, n, sizeof(data[0]), compare);

数组

哈希表

1. 哈希算法/哈希函数：将任意长度的二进制值串映射为固定长度的二进制值串的映射规则；
   • 其中所依据的目录称为“键”
   • 存放记录的数组称作散列表(Hash Table)
2. 哈希表是根据关键码的值而直接进行访问的数据结构
   • 比方说通过下标(key)访问数组的值时，数组可以视为哈希表,下标与数组存储的值可以成为一个键值对key-value,在jdk中被称为Entry
3. 常用于快速判断一个元素是否出现在集合中（提速）
4. 空间换时间

哈希碰撞

不同数据映射后成为相同的值

解决

拉链法

将冲突的值储存在同一列表当中，再在链表中检索

• 适当选择哈希表大小，减小哈希表可以降内存，缩短链表可以减少时间

线性探测法

要求:tableSize>dataSize

• 寻找空位存放多余数据

常见的三种哈希结构

数组、几何、映射

集合（set）