c++ 算法的時間復雜度

一般ACM或者筆試題的時間限制是1秒或2秒。
在這種情況下,C++代碼中的操作次數控制在 10^7為最佳。
下面給出在不同數據范國下,代碼的時間復雜度和算法該如何選擇:
1.n≤ 30,指數級別,dis+剪枝,狀態壓縮dp
2.n < 100 => 0 (n^2), floyd, dp
3.n ≤1000=>0(n^3), 0(nlogn), dp,二分
4. n ≤ 10000 => O(n * √n), 塊狀鏈表
5.n ≤100000=>0(nlogn)=>各種sort,線段樹、樹狀數組、set/map、 heap、dijkstra、 spta、求凸包、求半平面交、二分
6.n ≤1000000~>0(9),以及常數較小的O(nlogm)算法>hash、雙指針掃描、kemp、 AC自動機,常數比較小的o(nlogr)的做法:sort、樹狀數組、heap、 dijkstra、spfa
7.n ≤10000000 =>0(m),雙指針掃描、kmp、AC自動機、線性篩索數
8.n ≤10^9=>O(√n),判斷質數
9.n ≤ 10^18 => O(logn), 最大公約數

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/447060.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/447060.shtml
英文地址,請注明出處:http://en.pswp.cn/news/447060.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

簡單工廠模式實現計算器

#include <iostream> #include <vector> #include <string> #include <iostream> #include <map> using namespace std; #define __THROW_ZERO do {cerr << "The dividend is 0" << endl; exit(1);}while(0);/* 簡單工廠處…

TDengine安裝教程

TDengine安裝教程 前言 TDengine的安裝十分簡單&#xff0c;可以有以下三種安裝方式&#xff0c;源碼安裝、通過Docker容器進行安裝、通過安裝包進行安裝。但是使用源碼安裝較為復雜&#xff0c;通過docker的方式最為簡單&#xff0c;但是需要一定docker相關的知識&#xff0…

C++中size_t的學習

size_t的定義 size_t是一種數據相關的無符號類型&#xff0c;它被設計得足夠大以便能夠存儲內存中任意對象的大小。設計 size_t 就是為了適應多個平臺&#xff0c;size_t等效于unsigned short int 或者 unsigned long int 類型&#xff0c;這個過程是動態匹配的。在需要通過數…

策略模式解決商店打折問題

#include <bits/stdc.h> using namespace std; /*策略模式解決商店打折問題*/class Cashsuper { private:/* data */ public:virtual double addcash(double cash) 0;double Getresult(double money){return addcash(money);} };class Cashnormal : public Cashsuper {p…

android 軟件首次運行時引導頁左右滑動效果

很多手機軟件在安裝后首次運行都會進入到引導頁面&#xff0c;再次運行時會進入到主頁面。 多了不說了&#xff0c;先看效果圖&#xff1a; 代碼如下&#xff1a; main.xml <?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:an…

C++中size_type類型詳解

介紹 是和string類類型和vector類類型定義相關的類型&#xff0c;用以保存任意string對象或vector對象的長度&#xff0c;標準庫類型將size_type定義為unsigned類型string抽象意義是字符串&#xff0c; size&#xff08;&#xff09;的抽象意義是字符串的尺寸&#xff0c; str…

單一職責原則 實現貪吃蛇代碼的封裝

單一職責原則(SRP),就一個類而言&#xff0c;應該僅有一個引起它 變化的原因。 一個c語言的貪吃蛇代碼 如何使用單一職責原則封裝成c面向對象呢 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<string.h> #include<stdlib.h> #include <wi…

android ProgressBar實現掃描SD卡文件 + SimpleAdapter綁定ListView

代碼 activity_main.xml <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"xmlns:tools"http://schemas.android.com/tools"android:layout_width"match_parent"android:layout_height"match_parent"to…

C++標準庫函數begin和end函數

主要的目的 為了讓指針更加簡單、安全&#xff0c;引入了begin和end函數&#xff0c;這兩個函數和容器中兩個同名的成員函數類似。但是由于數組畢竟不是類類型&#xff0c;因此這兩個函數不是成員函數。正確的使用形式就是將數組作為他們的參數int ia[] {0,1,2,3,4,5,6,7,8,9…

dex分包之--------multidex包的配置使用

目錄&#xff1a;一、前言二、產生原因三、MultiDex的簡要原理四、MultiDex的使用 一、前言 首先說一下我遇到的情況&#xff0c;最近接手了一個項目是在已有的項目里進行更新添加一些功能&#xff0c;然后該項目導了N多的包&#xff0c;在我使用Android Studio的run”App”直…

C++ primer第六章函數的學習

介紹 首先介紹函數的定義和聲明&#xff0c;包括如何傳入參數以及函數如何返回結果。C語言允許使用重載函數&#xff0c;即幾個不同的函數可以使用向同一個名字。所以接下來介紹重載函數的方法&#xff0c;以及編譯器選擇如何從函數的若干重載的形式中選取一個與調用模板相互匹…

C語言指針作為函數參數 以及智能指針作為函數參數

總所周知指針作為函數參數傳遞的時候 傳遞的是指針的拷貝&#xff08;指針也是變量&#xff09; 這里提供四種指針的傳遞方法 改到實際的指針。 #include <stdio.h> #include <memory> #include <iostream> using namespace std; void test1(char **string)…

Android Studio打包和引用aar

一、簡介 Android 庫在結構上與 Android 應用模塊相同。它可以提供構建應用所需的一切內容&#xff0c;包括源代碼、資源文件和 Android 清單。不過&#xff0c;Android 庫將編譯到您可以用作 Android 應用模塊依賴項的 Android 歸檔 (AAR) 文件&#xff0c;而不是在設備上運行…

C++ primer第六章6.4函數的學習 之函數的重載

6.4 函數的重載 函數的名字相同但是形參的列表不同&#xff0c;將其稱之為重載函數 void print(const char *cp); void print(const int *beg,const int * end); void print(const int ia[],size_t size); 形如上面所展現的這樣&#xff0c;當調用這些函數的時候&#xff0c;…

C++有限狀態機的實現

//待完善 有限狀態機是一個很常用的技術&#xff0c;在流程控制和游戲AI中都比較實用&#xff0c;因為狀態機編程簡單又很符合直覺。與有限狀態機類似的是設計模式中的狀態模式。本文是參考《Programming Game AI by Example》 一、 記得最開始工作時候也接觸過有限狀態機&…

手勢希爾排序

void shell_sort(int *data, int length){int gap0;int i0,j0;for(gaplength/2;gap>1;gap/2){//組內插入排序for(igap;i<length;i){int temp data[i];for(ji-gap;j>0&&temp<data[j];jj-gap){data[jgap]data[j];}data[jgap]temp;}} }

Android之android.os.Build

一、類概述&#xff1a;從系統屬性中提取設備硬件和版本信息。 二、內部類&#xff1a; 1、Build.VERSION 各種版本字符串 2、Build.VERSION_CODES 目前已知的版本代碼的枚舉類 三、常量&#xff1a;UNKNOWN 當一個版本屬性不知道時所設定的值。其字符串值為 “unknown” 。 …

C++ unsigned char*轉化為string的形式

unsigned char*轉化為string int main(int argc,char **argv){//unsigned char * 轉化為string//參考鏈接 https://www.itdaan.com/tw/4ff531a5e6651468a5b7c6d95927ba3dunsigned char *foo;unsigned char str[] "Hello world";string strHH;foo str;strHH.append…

KMP算法面試題

面試題&#xff1a;寫一個在一個宇符串(n)中尋找一個子串&#xff08;m)第一個位置的函數。 10G的日志中&#xff0c;如何快速地查找關鍵字&#xff1f;