数据结构 一、绪论

# 绪论
## 数据结构
### 逻辑结构
- 线性结构：线性表、栈、队列
- 非线性结构：树、图、集合
### 存储结构

## 算法
### 定义
- 问题规模是n
- 若时间复杂度为O(n^2^)，则表明了执行时间与n^2^成正比

### 注意
- 算法原地工作是指算法所需的辅助空间是常量

### 5个特性
- 有穷性
- 确定性
- 可行性
- 输入
- 输出

### 目标
- 正确性
- 可读性
- 健壮性
- 效率和低存储量需求

## 时间复杂度
### 例1 (2011真题)
- 求下列的时间复杂度：
- ```
    x = 2;
    while(x<n/2>)
    x=2*x;
- 解答：
- ```
    设t为执行次数;
  => x=2^(t+1)^
  => t=log2(x) - 2
  => T(n) = O(log2(n))

### 例2 (2014真题)
- 求下列的时间复杂度：
- ```
    count = 0;
    for(k=1;k<=n;k*=2){
        for(j=1;j<=n;j*=2){
            count++;
            
        }
    }
- 解答：
- ```
    O(nlog2(n))

### 例3 (2017真题)
- 求下列的时间复杂度：
- ```
  int func(int n){
    int i = 0,sum = 0;
    while(sum<n){
        sum += ++i;
    }
    return i;
  }
- 解答：
- ```
  设t为执行次数;
  => sum = 1+2+3....+t = (t+1)t/2
  => t(t+1)/2 <n
  => t < n^(1/2)
  => T(n) = O(n^(1/2))



### 总结
- 遇事不决，直接设运行了t次即可
- 建立t与n的关系求出T(n)