算法时间复杂度

一:求1~n的连续整数和

#include<stdio.h>
#include<math.h>
#include<time.h>
//方法一:从1~n加和
long add1(long n) {
	int i, sum = 0;
	for (i = 1; i <= n; i++)
		sum += i;
	return sum;
}
void AddTime1(long n) {
	clock_t t;
	long sum;
	t = clock();
	sum = add1(n);
	t = clock() - t;
	printf("方法一结果:1~%d之和为:%ld\n", n, sum);
	printf("用时:%lf秒\n", ((float)t) / CLOCKS_PER_SEC);
}
//方法二:高斯法加和
long add2(long n) {
	int sum;
	sum = (n * (n + 1)) / 2;
	return sum;
}
void AddTime2(long n) {
	clock_t t;
	long sum;
	t = clock();
	sum = add2(n);
	t = clock() - t;
	printf("高斯法结果:1~%d之和为:%ld\n", n, sum);
	printf("用时:%lf秒\n", ((float)t) / CLOCKS_PER_SEC);
}
int main() {
	long n;
	printf("n(n大于1000000):");
	scanf_s("%ld", &n);
	if (n < 1000000)
		return 0;
	AddTime1(n);
	AddTime2(n);
}
不能理解为什么会变负数

二:常见算法时间函数的增长趋势分析

#include<stdio.h>
#include<math.h>
double log2(double n) {
	return log10(n) / log10(2);
}
long exponent(int n) {
	long s = 1;
	for (int i = 1; i <= n; i++)
		s *= 2;
	return s;
}
long factorial(int n) {
	long s = 1;
	for (int i = 1; i <= n; i++)
		s *= i;
	return s;
}
void fun(int n) {
	printf("log2(n) sqrt(n)  n       nlog2(n)   n^2	    n^3	     2^n		n!\n");
	printf("===========================================================================\n");
	for (int i = 1; i <= n; i++) {
		printf("%5.2f\t",log2(double(i)));
		printf("%5.2f\t",sqrt(i));
		printf("%5d\t",i);
		printf("%7.2f\t",i* log2(double(i)));
		printf("%5d\t", i*i);
		printf("%7d\t", i * i*i);
		printf("%8d\t",exponent(i));
		printf("%10d\n",factorial(i));
	}
}
int main() {
	int n = 10;
	fun(n);
	return 1;
}

关于return 的疑问

三:求素数的个数

#include<stdio.h>
#include<time.h>
#include<math.h>
bool prime1(long n) {
	long i;
	for (i = 2; i < n; i++)
		if (n % i == 0)
			return false;
	return true;
}
void PrimeTime1(long n) {
	clock_t t;
	long i, sum = 0;
	t = clock();
	for (i = 2; i <= n; i++)
		if (prime1(i))
			sum ++;
	t = clock() - t;
	printf("方法一:\n");
	printf("  结果:2~%d的素数个数:%d\n",n,sum);
	printf("  用时:%lf秒\n",((float)t)/CLOCKS_PER_SEC);
}
bool prime2(long n) {
	long i;
	for (i = 2; i < (int)sqrt(n); i++)
		if (n % i == 0)
			return false;
	return true;
}
void PrimeTime2(long n) {
	clock_t t;
	long i, sum = 0;
	t = clock();
	for (i = 2; i <= n; i++)
		if (prime2(i))
			sum ++;
	t = clock() - t;
	printf("方法二:\n");
	printf("  结果:2~%d的素数个数:%d\n", n, sum);
	printf("  用时:%lf秒\n", ((float)t) / CLOCKS_PER_SEC);
}
int main() {
	long n;
	printf("n(大于100000):");
	scanf_s("%d",&n);
	if (n < 100000)
		return 0;
	PrimeTime1(n);
	PrimeTime2(n);
	return 1;
}
回车后要等几秒,有运行时间

四:求连续整数阶乘的和

#include<stdio.h>
long sum(int n) {
	long sum = 0, fact = 1;
	for (int i = 1; i <= n; i++) {
		fact *= i;
		sum += fact;
	}
	return sum;
}
int main() {
	int n;
	printf("n(3--20):");
	scanf_s("%d",&n);
	if (n<3||n>20)
		return 0;
	printf("1!+2!+3!+.....+%d!=%ld\n",n,sum(n));
	return 1;
}

五:LeetCode7-整数反转

给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ,就返回 0。

int reverse(int x) {
    int rev = 0;
    while (x != 0) {
        if (rev < INT_MIN / 10 || rev > INT_MAX / 10) {
            return 0;
        }
        int digit = x % 10;
        x /= 10;
        rev = rev * 10 + digit;
    }
    return rev;
}

六:LeetCode1-两数之和

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    for (int i = 0; i < numsSize; ++i) {
        for (int j = i + 1; j < numsSize; ++j) {
            if (nums[i] + nums[j] == target) {
                int* ret = malloc(sizeof(int) * 2);
                ret[0] = i, ret[1] = j;
                *returnSize = 2;
                return ret;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}

关于C 库函数 – malloc(),参考:

https://www.runoob.com/cprogramming/c-function-malloc.html

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇