数据结构-时间空间复杂度

**数据结构与时间空间复杂度**

在计算机科学中，数据结构是指组织、存储和操作数据的方式。不同的数据结构可以有效地解决不同类型的问题。然而，在实际应用中，我们经常需要考虑到数据结构对系统性能的影响，即时间复杂度和空间复杂度。

**时间复杂度**

时间复杂度（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(n)：线性空间复杂度，表示算法所需的存储空间与输入大小成正比例。

**例子**

###例子一：线性搜索

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)):
 # Check if the current element is equal to the target if arr[i] == target:
 return i # Return the index of the target return -1 # Return -1 if the target is not found# Example usagearr = [2,5,8,12,16,23,38,56,72,91]
target =23index = linear_search(arr, target)

if index != -1:
 print(f"Target {target} found at index {index}.")
else:
 print(f"Target {target} not found in the array.")

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 # Check if the middle element is equal to the target if arr[mid] == target:
 return mid # Return the index of the target elif arr[mid] < target:
 low = mid +1 # Move the low pointer to the right half else:
 high = mid -1 # Move the high pointer to the left half return -1 # Return -1 if the target is not found# Example usagearr = [2,5,8,12,16,23,38,56,72,91]
target =23index = binary_search(arr, target)

if index != -1:
 print(f"Target {target} found at index {index}.")
else:
 print(f"Target {target} not found in the array.")