【数据结构】---时间复杂度与空间复杂度

**数据结构**

在计算机科学中，数据结构是指组织、存储和操作数据的方式。它是计算机程序设计中的一个基本概念，直接影响到程序的性能、效率和可维护性。

本文将讨论时间复杂度与空间复杂度这两个重要概念，以及它们在不同数据结构中的应用。

**时间复杂度**

时间复杂度（Time Complexity）是指算法执行所需的时间量，与输入大小的关系。它通常用大O符号表示，例如O(n)、O(log n)等。

常见的时间复杂度级别有：

* O(1)：恒定时间复杂度，表示算法在任何情况下都只需要常数时间。
* O(log n)：对数时间复杂度，表示算法的执行时间与输入大小的对数成正比。
* O(n)：线性时间复杂度，表示算法的执行时间与输入大小成正比。
* O(n log n)：线性对数时间复杂度，表示算法的执行时间与输入大小的乘积成正比。
* O(n^2)：平方时间复杂度，表示算法的执行时间与输入大小的平方成正比。

**空间复杂度**

空间复杂度（Space Complexity）是指算法所需的存储空间量，与输入大小的关系。它通常用大O符号表示，例如O(1)、O(n)等。

常见的空间复杂度级别有：

* O(1)：恒定空间复杂度，表示算法在任何情况下都只需要常数存储空间。
* O(log n)：对数空间复杂度，表示算法所需的存储空间与输入大小的对数成正比。
* O(n)：线性空间复杂度，表示算法所需的存储空间与输入大小成正比。

**例子**

###1. 线性搜索

def linear_search(arr, target):
 """
 Linear search algorithm.

 Args:
 arr (list): The input array.
 target: The target value to be searched.

 Returns:
 int: The index of the target value if found, -1 otherwise.
 """
 for i in range(len(arr)):
 if arr[i] == target:
 return i return -1# Example usagearr = [2,5,8,12,16,23,38,57,62,72,81]
target =23index = linear_search(arr, target)
print(f"Target {target} found at index {index}")

def binary_search(arr, target):
 """
 Binary search algorithm.

 Args:
 arr (list): The input array.
 target: The target value to be searched.

 Returns:
 int: The index of the target value if found, -1 otherwise.
 """
 low =0 high = len(arr) -1 while low <= high:
 mid = (low + high) //2 if arr[mid] == target:
 return mid elif arr[mid] < target:
 low = mid +1 else:
 high = mid -1 return -1# Example usagearr = [2,5,8,12,16,23,38,57,62,72,81]
target =23index = binary_search(arr, target)
print(f"Target {target} found at index {index}")

class HashTable:
 def __init__(self):
 self.size =10 self.table = [[] for _ in range(self.size)]

 def hash_function(self, key):
 return hash(key) % self.size def insert(self, key, value):
 index = self.hash_function(key)
 for i, (k, v) in enumerate(self.table[index]):
 if k == key:
 self.table[index][i] = (key, value)
 break else:
 self.table[index].append((key, value))

 def search(self, key):
 index = self.hash_function(key)
 for k, v in self.table[index]:
 if k == key:
 return v return None# Example usagehash_table = HashTable()
hash_table.insert("apple",5)
hash_table.insert("banana",7)

print(hash_table.search("apple")) # Output:5

class Stack:
 def __init__(self):
 self.stack = []

 def push(self, value):
 self.stack.append(value)

 def pop(self):
 if not self.is_empty():
 return self.stack.pop()
 else:
 raise IndexError("Stack is empty")

 def peek(self):
 if not self.is_empty():
 return self.stack[-1]
 else:
 raise IndexError("Stack is empty")

 def is_empty(self):
 return len(self.stack) ==0# Example usagestack = Stack()
stack.push(5)
stack.push(7)

print(stack.pop()) # Output:7

class Queue:
 def __init__(self):
 self.queue = []

 def enqueue(self, value):
 self.queue.append(value)

 def dequeue(self):
 if not self.is_empty():
 return self.queue.pop(0)
 else:
 raise IndexError("Queue is empty")

 def peek(self):
 if not self.is_empty():
 return self.queue[0]
 else:
 raise IndexError("Queue is empty")

 def is_empty(self):
 return len(self.queue) ==0# Example usagequeue = Queue()
queue.enqueue(5)
queue.enqueue(7)

print(queue.dequeue()) # Output:5

class Node:
 def __init__(self, value):
 self.value = value self.next = Noneclass LinkedList:
 def __init__(self):
 self.head = None def append(self, value):
 node = Node(value)
 if not self.head:
 self.head = node else:
 current = self.head while current.next:
 current = current.next current.next = node def traverse(self):
 values = []
 current = self.head while current:
 values.append(current.value)
 current = current.next return values# Example usagelinked_list = LinkedList()
linked_list.append(5)
linked_list.append(7)

print(linked_list.traverse()) # Output: [5,7]

class Node:
 def __init__(self, value):
 self.value = value self.left = None self.right = Noneclass Tree:
 def __init__(self):
 self.root = None def insert(self, value):
 if not self.root:
 self.root = Node(value)
 else:
 self._insert(value, self.root)

 def _insert(self, value, node):
 if value < node.value:
 if node.left:
 self._insert(value, node.left)
 else:
 node.left = Node(value)
 elif value > node.value:
 if node.right:
 self._insert(value, node.right)
 else:
 node.right = Node(value)

 def traverse(self):
 values = []
 self._traverse(values, self.root)
 return values def _traverse(self, values, node):
 if node:
 self._traverse(values, node.left)
 values.append(node.value)
 self._traverse(values, node.right)

# Example usagetree = Tree()
tree.insert(5)
tree.insert(7)

print(tree.traverse()) # Output: [5,7]

class Graph:
 def __init__(self):
 self.adjacency_list = {}

 def add_vertex(self, value):
 if value not in self.adjacency_list:
 self.adjacency_list[value] = []

 def add_edge(self, from_value, to_value):
 if from_value in self.adjacency_list and to_value in self.adjacency_list:
 self.adjacency_list[from_value].append(to_value)
 self.adjacency_list[to_value].append(from_value)

 def traverse(self):
 visited = set()
 values = []
 for value in self.adj