时间戳

首页 > 解决方案 > C#中数组类型数据结构的选择排序时间复杂度

c# - C#中数组类型数据结构的选择排序时间复杂度

问题描述

我已经在 C# 中使用数组（不是数组列表）实现了选择排序。大多数地方提到的选择排序的时间复杂度是 O(n^2)。

在下面的实现中，我将其视为 O(n^3)。有没有办法让它O（n ^ 2）？

在许多将选择排序的时间复杂度定义为 O(n^2) 的书籍中，我看到作者没有考虑数组中弹出或元素删除步骤的时间复杂度也是 O(n)。

using System;
public class SortArray
{
 public int[] SlectionSort(int[] arr)
 {
   int[] newarr = new int[arr.Length];
   for(int i=0; i<newarr.Length; i++)
   {
     int smallest_index = findSmallest(arr);
     newarr[i] = arr[smallest_index];
     arr = pop(arr, smallest_index);
   }
   return newarr;
 }

 public int findSmallest(int[] arr)
 {
   int smallest = arr[0];
   int smallest_index = 0;

   for(int i = 1; i < arr.Length; i++)
   {
     if(arr[i] < smallest)
     {
       smallest = arr[i];
       smallest_index = i;
     }
   }
   return smallest_index;
 }

 public static int[] pop(int[] arr, int index)
 {
   int size = arr.Length - 1; 
   int[] newArr = new int[size];
   int n = 0;
   for(int i=0; i < arr.Length; i++)
   {
     if( i > newArr.Length-1)
     { 
     break;
     }
   if(i < index)
   {
      newArr[i] = arr[i];
   }
   else 
   {
     newArr[i] = arr[i+1];
   }
 }
 return newArr;
 }
}

标签： c#algorithmdata-structuresselection-sort

解决方案

简短的版本是您通过强制它在固定（而不是动态）内存上操作来延迟选择排序。当您看到列出复杂性的通用算法时，这更像是一个指南而不是一个承诺。如果您不将数据结构与算法匹配，您将无法达到相同的时间复杂度上限。

我看到作者没有考虑数组中弹出或元素删除步骤的时间复杂度，这也是 O(n)。

这是您的输入组织不正确的迹象。举个更极端的例子，如果我坚持将我的列表存储在磁带上，那么数组访问是 O(n)，因为我需要等待磁带在读头下假脱机。这并不意味着算法更复杂。这意味着该实现在算法的方式中设置了障碍。

在某些情况下，这可能是必要的约束。但是对于问题中的情况，您只需要一个不需要算法来删除和插入项目的数据结构，例如List.

推荐阅读