数据结构，分析时间复杂度

链式存储结构的插入和删除不是时间复杂度为On吗
线性存储才是O1吧 这不是刚好是他们的优缺点吗

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7665018
• 这篇博客也不错, 你可以看下栈的最小值查找（O1）
• 除此之外, 这篇博客: 【数据结构其实真不难】算法分析中的 1.2.2常见的大O阶 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
  
  1.线性阶
  一般含有非嵌套循环涉及线性阶，线性阶就是随着输入规模的扩大，对应计算次数呈直线增长，例
  如：

  public static void main(String[] args) { 
      int sum = 0; 
      int n=100; 
      for (int i = 1; i <= n; i++) { 
          sum += i; 
      }
      System.out.println("sum=" + sum); 
  }

  上面这段代码，它的循环的时间复杂度为O(n),因为循环体中的代码需要执行n次

  2.平方阶

  一般嵌套循环属于这种时间复杂度

  public static void main(String[] args) { 
      int sum=0,n=100; 
      for (int i = 1; i <=n ; i++) { 
          for (int j = 1; j <=n ; j++) { 
              sum+=i; } 
          }
      System.out.println(sum);
  }

  上面这段代码，n=100，也就是说，外层循环每执行一次，内层循环就执行100次，那总共程序想

  要从这两个循环

  中出来，就需要执行100*100次，也就是n的平方次，所以这段代码的时间复杂度是O(n^2).

  3.立方阶

  一般三层嵌套循环属于这种时间复杂度

  public static void main(String[] args) { 
      int x=0,n=100; 
      for (int i = 1; i <=n ; i++) { 
          for (int j = i; j <=n ; j++) { 
              for (int j = i; j <=n ; j++) { 
                  x++; 
              } 
          }
       }
      System.out.println(x); 
  }

  上面这段代码，n=100，也就是说，外层循环每执行一次，中间循环循环就执行100次，中间循环

  每执行一次，最

  内层循环需要执行100次，那总共程序想要从这三个循环中出来，就需要执行100100100次，也就

  是n的立方，所

  以这段代码的时间复杂度是O(n^3).

  4.对数阶

  对数，属于高中数学的内容，我们分析程序以程序为主，数学为辅，所以不用过分担心。

  int i=1,n=100; 
  while(i<n){ 
      i = i*2; 
  }

  由于每次i*2之后，就距离n更近一步，假设有x个2相乘后大于n，则会退出循环。由于是2^x=n,得

  到x=log(2)n,所

  以这个循环的时间复杂度为O(logn);

  对于对数阶，由于随着输入规模n的增大，不管底数为多少，他们的增长趋势是一样的，所以我们

  会忽略底数。

  

  

  5.常数阶

  一般不涉及循环操作的都是常数阶，因为它不会随着n的增长而增加操作次数。例如：

  public static void main(String[] args) { 
      int n=100; 
      int i=n+2; 
      System.out.println(i); 
  }

  上述代码，不管输入规模n是多少，都执行2次，根据大O推导法则，常数用1来替换，所以上述代

  码的时间复杂度 为O(1)

  下面是对常见时间复杂度的一个总结：
• 以下回答来自chatgpt:

  链式存储结构的时间复杂度及与线性存储结构的优缺点比较

  链式存储结构是通过节点之间的指针相连的方式存储数据，而线性存储结构是将数据顺序存储在一片连续的存储空间内。

  对于链式存储结构，插入和删除操作的时间复杂度取决于节点的位置。如果需要插入或删除节点，需要先找到节点的前一个节点，然后通过修改指针的指向来完成操作。因此，链式存储结构的插入和删除操作的时间复杂度是O(n)，其中n为链表长度。

  相比之下，线性存储结构的插入和删除操作的时间复杂度是O(1)，只需要通过移动数组中的元素来完成操作。但是，线性存储结构需要预留一定的空间，如果空间不够，需要进行动态扩展或缩减操作，同时也会增加复杂度和开销。

  总体而言，链式存储结构比线性存储结构更加灵活，可以动态地管理内存空间。此外，链式存储结构可以方便地进行插入和删除操作，而线性存储结构则适用于需要随机访问元素的场合。因此，在实际应用中，需要根据具体的需求选择恰当的存储结构。

  参考代码:

  链式存储结构的节点定义：

  struct Node{
      int val;
      Node* next;
      Node(int x) : val(x), next(NULL) {}
  };
  

  实现链表的插入操作，需要先找到插入位置的前一个节点，然后将新节点插入到其后：

  void insert(Node* preNode, int value){
      if(preNode == NULL) return;
      Node* newNode = new Node(value);
      newNode->next = preNode->next;
      preNode->next = newNode;
  }
  

  实现链表的删除操作，需要先找到待删除节点的前一个节点，然后通过修改指针的指向来删除节点：

  void remove(Node* preNode){
      if(preNode == NULL || preNode->next == NULL) return;
      Node* target = preNode->next;
      preNode->next = target->next;
      delete target;
  }
  

  线性存储结构可以使用vector容器来实现，其中vector自带动态扩展和缩减的功能。在插入和删除元素时，需要移动后面的元素，因此需要O(n)的时间复杂度。但是，在随机访问元素时，vector的时间复杂度是O(1)。

  #include <iostream>
  #include <vector>
  using namespace std;
  
  int main(){
      vector<int> vec;
      vec.push_back(1);   //在数组末尾插入元素
      vec.push_back(2);
      vec.push_back(3);   
      vec.insert(vec.begin() + 1, 4);  //在指定位置插入元素
      vec.erase(vec.begin() + 2);     //删除指定位置的元素
      for(int i = 0; i < vec.size(); ++i){
          cout << vec[i] << " ";
      }
      return 0;
  }
  

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^

线性存储的定位（读）操作的复杂度是O(1)
插入可不是，需要从后往前搬动数据，是O(n)