时间戳

首页 > 解决方案 > 这个算法是 O(n^2) 还是 O(n)

c# - 这个算法是 O(n^2) 还是 O(n)

问题描述

我有 2 个清单：

该算法需要通过 eventType 过滤事件。

问题是，algo1 O(n^2) 和 algo2 O(n) 是什么？或者他们都是O（n）？

我还在代码中标记了代码各个点的O复杂度，请确认它们是否正确p1.1 ， p1.2 ， p2.1 ， p2.2？

我根据每个算法的最高复杂度来确定每个算法的最终 O 复杂度，我的假设是它们都是 O(n)。

请添加任何进一步的观察，也与可能看起来具有不同 O 复杂性的糖代码有关。

我假设 select 语句没有并行运行，或者代码的任何其他部分都没有并行运行。

发生了 2 次主列表迭代，一个循环遍历固定数量的元素（EventType 列表），而另一个循环遍历理论上可以认为是无限的元素（Events 列表）。出于这个主要原因，我认为 ALGO1 和 ALGO2 都是 O(n)。如果我错了，请纠正我。

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp2
{
    class Program
    {
        static void Main(string[] args)
        {
            //Algo 1 is O(n) or O(n^2)?
            var resp1 = FilterEventsAlgo1(GetEvents(), GetEventTypesToFilter());
            //Algo 2 is O(n) or O(n^2)?
            var resp2 = FilterEventsAlgo2(GetEvents(), GetEventTypesToFilter());
        }

        static List<EventResponse> FilterEventsAlgo1(List<Event> events, List<EventType> eventTypesToFilter)
        {
            var filteredEvents = new List<EventResponse>();
            //p1.1 is O(n)?
            foreach (Event ev in events)
            {
                //p1.2 is O(1)?
                if (eventTypesToFilter.Any(x => x == ev.EventType))
                {
                    filteredEvents.Add(new EventResponse());
                }
            }
            return filteredEvents;
        }

        static List<EventResponse> FilterEventsAlgo2(List<Event> events, List<EventType> eventTypesToFilter)
        {
            //p2.1 is O(1)?
            events.RemoveAll(x => !eventTypesToFilter.Contains(x.EventType));
            //p2.2 is O(n)?
            var filteredEvents = events.Select(x => new EventResponse()).ToList();

            return filteredEvents;
        }

        static List<Event> GetEvents()
        {
            //... Theretically the number of elements CAN VARY TO A GREATER NUMBER up to infinity
            List<Event> Events = new List<Event> {
                new Event(EventType.Type1),
                new Event(EventType.Type2),
                new Event(EventType.Type3),
                new Event(EventType.Type3),
                new Event(EventType.Type3)
            };
            return Events;
        }

        static List<EventType> GetEventTypesToFilter()
        {
            //... The number of elements in this list is always limited to max 3, can be seen as a constant number of elements
            List<EventType> EventTypesToFilter = new List<EventType> {
                EventType.Type1,
                EventType.Type2,
            };
            return EventTypesToFilter;
        }

    }

    class Event
    {
        public EventType EventType { get; set; }
        public Event(EventType eventType)
        {
            this.EventType = eventType;
        }
    }

    class EventResponse
    {

    }


   
    enum EventType
    {
        Type1,
        Type2,
        Type3
    }
}

标签： c#algorithmbig-o

解决方案

这些算法非常相似，并且都具有相同的复杂性。

如果您想以有意义的方式说明这种复杂性，那么您会说它是 O(events.size() * eventTypesToFilter.size()) 或 O(n * m)，其中 n 和 m 是这些大小。

如果您真的必须仅根据总输入大小来说明它，那么它将是 O(n 2 )... 但实际上您不会那样做。如果你说 O(n * m)，那么调用者知道如果他传递给你一个固定大小的事件类型列表，那么他的算法可以是 O(n)，并且他对调用你的代码的成本有所了解会随着“固定”大小的增加而增加。

推荐阅读