Skip to content

Latest commit

 

History

History
232 lines (182 loc) · 5.13 KB

chp1_basic.md

File metadata and controls

232 lines (182 loc) · 5.13 KB

🚗...

Chapter1 Baisc Concept

  • Big O[实际性能上界，如何定义的]
  • 算法分析[给段程序，给出BigO的值]

性能分析

空间复杂度

  • 固定空间: 代码空间， 简单变量空间， 常数空间等

  • 可变空间:

    • 结构变量所需空间， 依赖于问题特殊实例 + 引用变量所需空间， 依赖于实例特性
    • 引用变量所需空间， 依赖于实例特性
    • 递归栈所需空间，依赖于实例特性

  • S(P) = c + Sp

时间复杂度

定义

  • : g(n) 是 f(n)的上界
  • : g(n) 是 f(n)的下界
  • : g(n) 即是 f(n)的上界，又是f(n)

程序步

在语法或语义上有意义的程序片段，且该片段的执行时间不依赖于实例特性

  1. 注释语句: 0；
  2. 声明语句：0；
  3. 表达式与赋值语句：1；
  4. 循环语句：只考虑这类语句的控制部分的程序步数
  • for(init; expression1; expression2) : 1
  • while(expression) do or do...while(expression): 程序步数等于其表达式的程序步数
  1. switch语句：
switch(expression) {
case cond1: statement1
case cond2: statement2
.
.
default: statement
}
  • 首部时间开销等于表达式开销
  • 每个条件语句的时间开销等于该条件语句的时间开销加之前条件语句时间开销
  1. if-else语句：
if (expression) statement1;
else statement2;

每个部分程序步数分别根据expression statement1 和 statement2来确定

  1. 函数调用：1（除非该函数调用涉及实例特性的按值传参）
  2. 内存管理语句： new delete sizeof... : 1
  3. 函数语句：0
  4. 转移语句：continue, break, goto, return... : 1

计算程序步的两种方法

Source:

float Sum(float* a, const int n)
{
  float s = 0;
  for(int i = 0; i < n; i++)

    s += a[i];

  return s;
}
计数器法：引入变量count

Add Count:

float Sum(float* a, const int n)
{
  float s = 0;
  count++; //count is global
  for(int i = 0; i < n; i++)
  {
    count++; //for for
    s += a[i];
    count++; //for assignment
  }
  count++; //for last time of for
  count++; //for return
  return s;
}

简化：

float Sum(float* a, const int n)
{
  for(int i = 0; i < n; i++)

    count += 2;

  count += 3;
}
列表法

s/e: 一条语句每次执行程序步数
FS: 语句频率(Frequence of Statement)
PS: 程序步数(Process Steps)

Row s/e FS PS
1 0 1 0
2 1 1 1
3 1 n+1 n+1
4 1 n n
5 1 1 1
6 0 1 0
总的 程序 步数 2n+ 3

封装

访问权限

  • public: 谁都可以
  • protect: 类及其子类
  • private: 只有当前类

友元

  • friend:

    • 友元函数
      class Node {
  private:
      int key;
      Node* next;
      /* Other members of Node Class */
      friend int LinkedList::search();
      // Only search() of linkedList
      // can access internal members
  };

这样的话，函数search虽不是Node类的方法， 但可以直接访问Node类的私有变量

  • 友元类 
      #include <iostream>
  class A {
  private:
      int a;

  public:
      A() { a = 0; }
      friend class B; // Friend Class
  };

  class B {
  private:
      int b;

  public:
      void showA(A& x)
      {
          // Since B is friend of A, it can access
          // private members of A
          std::cout << "A::a=" << x.a;
      }
  };

  int main()
  {
      A a;
      B b;
      b.showA(a);
      return 0;
  }

这样B中所有函数都是A的友元函数，都可以访问A的私有变量

重载运算符

  1. "<<"运算符
ostream& operator<<(ostream& os, Rectangle& r)
{
  os<<"Position is : "<<r.xLow<<" ";
  os<<r.yLow<<endl;
  os<<"Height is : "<<r.height<<endl;
  os<<"Width is : "<<r.width<<endl;
  return os;
}
  1. 二元运算符
bool Rectangle::operator==(const Rectangle& s)
{
  if(this == &s) return true;
  if((xLow == s.xLow) && (yLow == s.yLow)
    &&(height == s.height) && (width == s.width))
    return true;
  else return false;
}