Har en FFT av O(n) nåt värde idag?

med tanke på snabba processorer. En FFT är normalt O( log(n)*n ).

Naturligtvis är det av intresse. Men det är troligtvis omöjligt.

För en signal med samma frekvensinnehåll genom hela signalen är jag rätt säker på att jag kan skriva en med O(n) och kanske t.o.m mindre. Är det trivialt?

Om frekvensinnehållet varierar är jag inte säker, men jag håller på att tänka på det.

Lite oklart vad du menar med "samma frekvensinnehåll". Tänker du dig att det bara är en sinusfunktion och du skall utröna dess frekvens och amplitud?

En algoritm som har mindre än O(N) kan inte ens behandla varje element en enda gång och jag har svårt att se hur man skall kunna göra något vettigt av det.

Det kan vara flera frekvenser så klart. Men de ändras inte i signalen.

Vad menar du med att frekvenserna inte ändras?

Om man mäter vägguttaget får man en frekvens som inte ändras. Om man mäter ljudet när jag pratar ändras frekvensen.

Jag är tyvärr fortfarande oförstående med vad du menar. Inget i FFT är "tidsberoende" på det sättet som jag tror att du menar, om jag inte missförstår dig på något sätt. Så jag förstår inte varför de exempel du tar upp är relevanta. Kanske underlättar att förstå vad du gör om du beskriver lite hur du får det till O(n)?

Det handlar alltså om signalen man vill analysera. Om signalen har samma frekvensinnehåll genom hela signalen eller inte.

Går det att avgöra vilket frekvensinnehåll en signal har vid tidsögonblicket t?

Eller är frekvensinnehåll något som man pratar om, och kan räkna ut över en tidsperiod?

Om man räknar fram ett frekvensinnehåll över en tidsperiod. Hur kan man avgöra om den ändras med tiden inom den tidsperioden..?

Det du vill göra är då inte en FFT utan just som jag misstänkte bara ett sätt att kunna analysera en sinuskurva. En Fouriertransform skall kunna analysera alla signaler.

Nej, inte bara en sinuskurva. Flera frekvenser på en gång.