c#

我有 2 个列表：

• 事件列表（可以具有从 1 个元素到无穷大的可变大小）
• EventTypesToFilter 列表（始终固定/恒定大小为 1 到最多 3 个元素）

该算法需要按事件类型过滤事件。

问题是，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 列表），而另一个循环迭代多个理论上可以被认为是无限的元素（事件列表）。出于这个主要原因，我认为 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
    }
}

回答