数据结构

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

推导大O阶：
1.用常数1取代运行时间中的所有加法常数
2.在修改后的运行次数函数中，只保留最高阶
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数

for(int i = 0; I < n; i++) {
   /* 时间复杂度为O(1)的程序*/
}
时间复杂度为O(n)

int count = 1;
while(count < n) {
  count = count * 2;
  /* 时间复杂度为O(1)的程序*/
}
由于每次count乘以2之后，就距离n更近了一份。也就是说 有多少个2相乘后大于n,则会退出循环。 由2^x = n, 得到 x = log2^n, 所以时间复杂度为 O(log n)

for(int i = 0; i< m; i++) {
   for(int j = 0; j < n; j++) {
     /* 时间复杂度为O(1)的程序*/
  }
}
时间复杂度为 O(m x n)

int i , j;
for(i = 0; i< n; i++) {
   for( j = i; j < n; j++) {
     /* 时间复杂度为O(1)的程序*/
  }
}
时间复杂度为 O(n^2);

for(int i = 0; i < n; i ++) {
   function(i);
}

void function(int count) {
   print(count);
}
时间复杂度为O(n);

for(int i = 0; i < n; i ++) {
   function(i);
}

void function(int count) {
   int j;
   for( j = count; j < n; j++) {
        /* 时间复杂度为O(1)的程序*/
   }
}
时间复杂度为O(n^2);